CF161E Polycarpus the Safecracker

Polycarpus 有 $t$ 个保险箱。每个保险箱的密码是一个只包含十进制数字 $0$ 到 $9$ 的方阵（每个保险箱的密码矩阵大小可能不同）。然而，Polycarpus 把所有的密码都给忘了，所以现在他需要恢复这些密码。 Polycarpus 喜爱质数，因此在选择密码矩阵时，他在每个矩阵的每一行都写下了一个质数。令他惊讶的是，所有这些矩阵都是对称矩阵（即转置后与原矩阵相同）。多年后，Polycarpus 恼火地发现他只记得每个密码矩阵第一行所写的质数 $p_i$。 对于每个保险箱，请你计算有多少种可能的矩阵可以作为它的密码。 数字 $p_i$ 的位数决定了第 $i$ 个矩阵的行和列数。一个质数可以在同一矩阵的多行出现，也可以在不同的矩阵出现。写在矩阵非第一行的质数允许有前导零。

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

输出 $t$ 行，第 $i$ 行输出一个整数，表示可以作为第 $i$ 个保险箱密码的矩阵个数。

这是第二个保险箱的一种可能的密码矩阵： `

239

307

977

` 这是第四个保险箱的一种可能的密码矩阵： `

9001

0002

0002

1223

` 由 ChatGPT 5 翻译