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 ≤ d_i ≤ 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