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
2017-12-26 14:56:18 Michael Kharitonov
@manya_cod4: this problem is harder than you think, you need to sieve primes less than 1e9. First solve TDPRIMES, then PRIMES2 and then try this problem. The simple implementation of Segmented sieve of Eratosthenes can be found at http://primesieve.org/segmented_sieve.html
And I don't think JAVA is fast enough, use C/C++ like all the people who got AC at the moment.

Last edit: 2017-12-26 15:09:13
2017-12-26 13:24:19
Hi All. I used modified sieving technique for finding the primes till 9999999, and for all the permutation, i first sorted the array and used algorithm for finding the next permutation iteratively. still I am getting TLE. optimization needs to be done to sieving technique or finding the permutations? Thanks
2017-12-25 17:09:56
I am using modified sieving technique. And for permuting for the combinations, i am using recursive function. I am getting TLE. anyone can tell, where is modification is needed in this problem?
2017-12-24 11:39:31
@zimpha: Good day to you. Thanx, very nice to hear it from such "programming-beast" ...++Very nice time! Good Luck & Wish you a nice day!
2017-12-24 07:19:17 zimpha
@morass nice problem, I learn a lot advanced sieving techniques from this problem.

Last edit: 2017-12-24 07:19:54
2017-12-23 18:17:57
@barishnamazov: Good day to you. I guess it is correct now, since god has already solved it.

beside this, try following input:

1
2 1 1

it shall yield "1"

(also there are a few other submissions which are correct yet slow, passing this test-case)

Wish you a Nice Day and Good Luck!
2017-12-23 11:59:10
Please check tests again..
2017-12-23 10:55:33
Good day to you,

I apologize - there was a mistake in test-data. Hope it is repaired now. Sorry for the inconvenience!

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