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 some funny signs, which contains a few digits. The digits on the sign could be arbitrarily permuted (yet not added or 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