Shortening codes

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<100 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 you (also) like optimizing for speed, you may try the classical version.