CF161E.Polycarpus the Safecracker

Polycarpus has t safes. The password for each safe is a square matrix consisting of decimal digits '0' ... '9' (the sizes of passwords to the safes may vary). Alas, Polycarpus has forgotten all passwords, so now he has to restore them.

Polycarpus enjoys prime numbers, so when he chose the matrix passwords, he wrote a prime number in each row of each matrix. To his surprise, he found that all the matrices turned out to be symmetrical (that is, they remain the same after transposition). Now, years later, Polycarp was irritated to find out that he remembers only the prime numbers p__i, written in the first lines of the password matrices.

For each safe find the number of matrices which can be passwords to it.

The number of digits in p__i determines the number of rows and columns of the i-th matrix. One prime number can occur in several rows of the password matrix or in several matrices. The prime numbers that are written not in the first row of the matrix may have leading zeros.

Polycarpus 有 $t$ 个保险箱。每个保险箱的密码是一个由十进制数字 '0' 到 '9' 构成的方阵（各保险箱密码的尺寸可能不同）。不幸的是，Polycarpus 忘记了所有密码，因此现在他必须恢复这些密码。

Polycarpus 喜欢素数，因此在选择矩阵密码时，他在每个矩阵的每一行中都写入了一个素数。令他惊讶的是，他发现所有矩阵都是对称的（即，矩阵在转置后保持不变）。如今，多年之后，Polycarpus 沮丧地发现，他仅记得各密码矩阵第一行中所写的素数 $p_i$。

对每个保险箱，求出可作为其密码的矩阵个数。

$p_i$ 的位数决定了第 $i$ 个矩阵的行数与列数。同一个素数可在密码矩阵的多行中出现，也可在多个矩阵中出现。写在矩阵非第一行中的素数可以包含前导零。

The first line of the input contains an integer t (1 ≤ t ≤ 30) — the number of safes. Next t lines contain integers p__i (10 ≤ p__i ≤ 99999), p__i is a prime number written in the first row of the password matrix for the i-th safe. All p__i's are written without leading zeros.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 30$）—— 表示保险箱的数量。接下来的 $t$ 行每行包含一个整数 $p_i$（$10 \leq p_i \leq 99999$），其中 $p_i$ 是第 $i$ 个保险箱的密码矩阵第一行中所写的质数。所有 $p_i$ 均不带前导零。

Print t numbers, the i-th of them should be the number of matrices that can be a password to the i-th safe. Print the numbers on separate lines.

输出 t 个数，其中第 i 个数应为能够作为第 i 个保险箱密码的矩阵个数。每个数单独占一行。

Here is a possible password matrix for the second safe:

239
307
977

Here is a possible password matrix for the fourth safe:

9001
0002
0002
1223

第二个保险箱的一个可能的密码矩阵如下：

239
307
977

第四个保险箱的一个可能的密码矩阵如下：

9001
0002
0002
1223