Submit | All submissions | Best solutions | Back to list |

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

Added by: | Morass |

Date: | 2017-12-22 |

Time limit: | 6s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | C CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 JAVA PYTHON PYPY PYTHON3 |