SP8591 PRIMPERM - Prime Permutations

Given two positive integers n and m, we call m a prime permutation of n, if m is prime and can be obtained by zero or more permutations of the digits of n. Permutations with leading zeros are invalid.

Input starts with a positive integer t

For every n print the number of distinct prime permutations of n in a single line.