PRIMPERM - Prime Permutations

### 题目描述 $t$ 组数据，每组数据给定一个整数 $n$，求 $n$ 的排列中有多少个排列是质数。 ### 输入格式 共 $t+1$ 行： 第一行为一个整数 $t$。 第 $2\sim t+1$ 行每行一个整数 $n$。 ### 输出格式 共 $t$ 行，每行一个整数表示 $n$ 的排列中有多少个排列是质数。 ### 数据范围 $t<10^4$，$n<10^7$

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<10 $ ^{4} $ in a single line, then t lines follow. Each of the t lines contains one positive integer n<10 $ ^{7} $ .

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

2
13
110

2
1