ADAPRIME - Ada and Prime

no tags 

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!


The first line of input will contain 1 ≤ T ≤ 10000, the number of test-cases.


The next T lines will contain 1 ≤ D ≤ 9, the number of digits on sign, followed by D digits 0 ≤ di ≤ 9


For each test-case, output the number of distinct primes which could be generated on given sign.

Example Input

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


hide comments
[Lakshman]: 2017-12-31 12:28:58

@Morass can you please have a look at my solution I am really not sure why I am getting TLE.

EDIT:: Finally AC. Precomputation and boost::unordered_map helped.

Last edit: 2018-01-06 08:35:46
Michael Kharitonov: 2017-12-31 12:07:22

The story could've been more convincing.

Last edit: 2018-01-08 01:53:31
Michael Kharitonov: 2017-12-31 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]: 2017-12-31 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: 2018-01-26 14:04:57
Michael Kharitonov: 2017-12-29 23:40:22

tip of the day: use Built-in Functions Provided by GCC -
__builtin_popcount & __builtin_ctz & __builtin_ffs are especially useful in this task.

Last edit: 2017-12-29 23:44:52
Howard Roark: 2017-12-29 02:48:18

aaargh, wrong answer! But it works for all the test cases...

manya_cod4: 2017-12-29 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: 2017-12-29 02:15:47
[Lakshman]: 2017-12-28 18:16:23

Last edit: 2018-01-01 17:14:35
manya_cod4: 2017-12-27 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: 2017-12-27 16:28:53
manya_cod4: 2017-12-26 19:23:43

@Michael. Thanks. I was also thinking i was way over my head. Surely, i will try those problems now.

Last edit: 2017-12-27 16:25:55

Added by:Morass
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)