PRIMPERM - Prime Permutations

no tags 

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 your solution times out, you may try the tutorial version with a longer time limit.


hide comments
ht321ht: 2023-07-20 15:58:42

em,有人吗

Mitch Schwartz: 2015-01-18 21:58:19

Hmm, I narrowly got AC in the time limit in 2011 but it turned to TLE after cluster change, guess I'll have to revisit.

Edit: There were some funny things going on in that old code.

Last edit: 2015-01-18 23:39:41

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