← 返回题目列表

Codeforces · 161/E

E. 保险箱窃贼波利卡普斯

中文机器翻译题面 查看原题

Polycarpus 有 t 个保险箱。每个保险箱的密码都是由十进制数字“0”...“9”组成的方阵(保险箱密码的大小可能有所不同)。唉,波利卡波斯忘记了所有密码,所以现在他必须恢复它们。

Polycarpus很喜欢素数,所以他在选择矩阵密码时,在每个矩阵的每一行都写了一个素数。令他惊讶的是,他发现所有矩阵都是对称的(即转置后它们保持不变)。多年后的现在,波利卡普很恼火地发现他只记得写在密码矩阵第一行的质数 pi。

对于每个保险箱,找到可以作为其密码的矩阵数量。

pi 中的位数决定了第 i 个矩阵的行数和列数。一个素数可以出现在密码矩阵的多行或多个矩阵中。不在矩阵第一行中写入的素数可能有前导零。

输入

输入的第一行包含一个整数 t (1 ≤ t ≤ 30) — 保险箱的数量。接下来的 t 行包含整数 pi (10 ≤ pi ≤ 99999),pi 是第 i 个保险箱的密码矩阵第一行中写入的素数。所有 pi 的书写都不带前导零。

输出

打印t个数字,其中第i个应该是可以作为第i个保险箱密码的矩阵的数量。将数字打印在单独的行上。

示例

输入 #1

4
11
239
401
9001

输出 #1

4
28
61
2834

注意

这是第二个保险箱的可能密码矩阵:

这是第四个保险箱的可能密码矩阵: