SP33932 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!

The first line of input will contain **1 , the number of test-cases.** The next **T** lines will contain **1 , the number of digits on sign, followed by **D** digits 0**

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