Given two positive integers n and m, we call m a prime permutation of n, if m is prime and can be obtained by zero or more permutations of the digits of n. Permutations with leading zeros are invalid.

Input

Input starts with a positive integer t<10⁴ in a single line, then t lines follow.
Each of the t lines contains one positive integer n<10⁷.

Output

For every n print the number of distinct prime permutations of n in a single line.

Example

Input:
2
13
110
Output:
2
1

Hint:If your solution times out, you may try the tutorial version with a weaker time limit.