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
注意
这是第二个保险箱的可能密码矩阵:
这是第四个保险箱的可能密码矩阵: