TPRIMPER - Prime Permutations (easy)

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<104 in a single line, then t lines follow.
Each of the t lines contains one positive integer n<107.

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 the time limit is too long, then try the classical version.


Added by:numerix
Date:2011-03-22
Time limit:5s
Source limit:10000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.