ADAPRIME  Ada and Prime
As you might already know, Ada the Ladybug is a farmer. She grows many vegetables and trees and she wants to distinguish between them. For this purpose she bought a funny signs, which contains a few digits. The digits on the sign could be arbitrarily permuted (yet not added/removed). Ada likes prime numbers so she want the signs to be prime (and obviously distinct). Can you find the number of signs with prime number which could be obtained?
NOTE: Number can't have leading zero!
Input
The first line of input will contain 1 ≤ T ≤ 10000, the number of testcases.
The next T lines will contain 1 ≤ D ≤ 9, the number of digits on sign, followed by D digits 0 ≤ d_{i} ≤ 9
Output
For each testcase, output the number of distinct primes which could be generated on given sign.
Example Input
5 1 9 3 1 2 3 5 1 2 0 8 9 7 1 0 6 5 7 8 2 5 1 2 7 3 1
Example Output
0 0 11 283 15
hide comments
[Lakshman]:
20171231 12:28:58
@Morass can you please have a look at my solution I am really not sure why I am getting TLE.


Michael Kharitonov:
20171231 12:07:22
The story could've been more convincing. Last edit: 20180108 01:53:31 

Michael Kharitonov:
20171231 11:50:13
@Lakshman: after sieve I used hash table with open addressing and processed only changed digits. Expected complexity O(p*log(log(p))) p=pi(1e9)=50847534 

[Lakshman]:
20171231 11:19:00
What is the expected complexity? The best I can come up with is (Sieve ) $O(n log log n)$ + (precompute all possible permutation of primes) $O(p log p) $where n = 1e9 and p = 50847534 total primes less than 1e9 and answer in O(1). Last edit: 20180126 14:04:57 

Michael Kharitonov:
20171229 23:40:22
tip of the day: use Builtin Functions Provided by GCC  https://gcc.gnu.org/onlinedocs/gcc/OtherBuiltins.html


Howard Roark:
20171229 02:48:18
aaargh, wrong answer! But it works for all the test cases... 

manya_cod4:
20171229 02:15:34
@[Lakshman] : Hi. I am not yet able to solve this problem as I am getting TLE. But in your case you are missing two numbers. They are 11273,12713. Hope that helps. Last edit: 20171229 02:15:47 

[Lakshman]:
20171228 18:16:23
Last edit: 20180101 17:14:35 

manya_cod4:
20171227 16:25:30
@Michael. Thanks. I learned a lot solving TDPRIMES and PRIMES. And i used c++ as you suggested. But still my solution is almost 10 times slower than yours. will try to optimize it further, but i dont think i will even reach close to that. Now I will again try to solve this problem. Last edit: 20171227 16:28:53 

manya_cod4:
20171226 19:23:43
@Michael. Thanks. I was also thinking i was way over my head. Surely, i will try those problems now. Last edit: 20171227 16:25:55 
Added by:  Morass 
Date:  20171222 
Time limit:  6s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 