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.