Preparing NOJ

# An Industrial Spy

10000ms 65536K

## Description:

Industrial spying is very common for modern research labs. I am such an industrial spy { don't tell anybody! My recent job was to steal the latest inventions from a famous math research lab. It was hard to obtain some of their results but I got their waste out of a document shredder.

I have already reconstructed that their research topic is fast factorization. But the remaining paper snippets only have single digits on it and I cannot imagine what they are for. Could it be that those digits form prime numbers? Please help me to nd out how many prime numbers can be formed using the given digits.

## Input:

The rst line of the input holds the number of test cases c (1 <= c <= 200). Each test case consists of a single line. This line contains the digits (at least one, at most seven) that are on the paper snippets.

## Output:

For each test case, print one line containing the number of di erent primes that can be reconstructed by shuing the digits. You may ignore digits while reconstructing the primes (e.g., if you get the digits 7 and 1, you can reconstruct three primes 7, 17, and 71). Reconstructed numbers that (regarded as strings) di er just by leading zeros, are considered identical (see the fourth case of the sample input).

## Sample Input:

41712765439999999011

## Sample Output:

3133602

## Note:

Info

Provider NOJ

Code NOJ1128

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet