Polycarpus the Safecracker

题意翻译

Polycarpus 的保险箱 题目描述 Polycarpus 有 t 个保险箱。 每个保险箱的密码都是由十进制数字'0'...'9'组成的正方形矩阵(每个保险箱矩阵密码的大小可能不同)。不幸的是，Polycarpus 忘记了所有的密码，所以现在他需要找回密码。 Polycarpus 喜欢质数(素数)，所以当他设置矩阵密码时，他每个在矩阵的每一行都写下了一个质数。令他吃惊的是，这些矩阵竟然是对称的(即交换位置后矩阵不变)。现在，过了几年，Polycarpus 生气地发现自己只能记得质数 Pi ，那些写在所有密码矩阵的第一行的质数。 对于每一个保险箱，找到密码矩阵中的数字，就找到了密码。 质数 Pi 的位数决定了第 i 个密码矩阵的行数和列数。一个质数可能出现于密码矩阵的几行中或几个密码矩阵中。那些没有写在密码矩阵第一行的质数可能具有前导零(即数字前面加有’0’)。 输入输出格式 输入格式 输入的第一行包括一个整数 t (1<=t<=30) —— 保险箱的数量。下面 t 行每包含一个整数 Pi (10<=Pi<=99999)， Pi 是第 i 个保险箱密码矩阵第一行的那个质数。所有 Pi 都没有前导零。 输出格式 输出 t 个数字，其中第 i 个数字是第 i 个保险箱可以作为此保险箱矩阵密码的矩阵数量。每行输出一个数字。 说明 这是样例中第二个保险箱密码矩阵的所有可能：<br></br>239<br></br>307<br></br>977<br></br> 这是样例中第四个保险箱密码矩阵的所有可能：<br></br>9001<br></br>0002<br></br>0002<br></br>1223 <br></br>

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

输入样例 #1

4
11
239
401
9001

输出样例 #1

4
28
61
2834

说明

Here is a possible password matrix for the second safe: `<br></br>239<br></br>307<br></br>977<br></br>`Here is a possible password matrix for the fourth safe: `<br></br>9001<br></br>0002<br></br>0002<br></br>1223 <br></br>`