Bạn được nhận ~k \le 7~ chữ số ngẫu nhiên.

Yêu cầu: Dùng các chữ số bạn nhận được, hãy đếm xem có thể tạo ra được bao nhiêu số nguyên tố khác nhau.

Input

• Dòng đầu tiên là số ~T \le 10~ - số lượng test.
• ~T~ dòng tiếp theo, mỗi dòng gồm ~k~ chữ số tương ứng với một yêu cầu.

Output

• ~T~ dòng là kết quả của các test tương ứng theo thứ tự.

Sample Input 1

2
17
9999999

Sample Output 1

3
0

Giải thích

• Với ~2~ chữ số ~1,7~, tạo ra được 3 số nguyên tố là ~7, 17, 71~.
• Với ~7~ chữ số ~9~, không tạo ra được số nguyên tố nào.