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 test-cases.

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

Output

For each test-case, 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

Added by:Morass
Date:2017-12-22
Time limit:6s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2022-10-06 09:41:45
Amazing problem! AC in one go.
2017-12-31 12:28:58 [Lakshman]
@Morass can you please have a look at my solution I am really not sure why I am getting TLE.
Thanks.

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

Last edit: 2018-01-06 08:35:46
2017-12-31 12:07:22 Michael Kharitonov
The story could've been more convincing.

Last edit: 2018-01-08 01:53:31
2017-12-31 11:50:13 Michael Kharitonov
@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
2017-12-31 11:19:00 [Lakshman]
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
2017-12-29 23:40:22 Michael Kharitonov
tip of the day: use Built-in Functions Provided by GCC - https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html
__builtin_popcount & __builtin_ctz & __builtin_ffs are especially useful in this task.

Last edit: 2017-12-29 23:44:52
2017-12-29 02:48:18 Howard Roark
aaargh, wrong answer! But it works for all the test cases...
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
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
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.