跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F2930. Polycarpus the Safecracker

  • ID: 2936
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 枚举
  • 动态规划
  • 算法思想
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Polycarpus the Safecracker

题目描述

E. Polycarpus the Safecracker
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 pi, 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 pi 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.

Input

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

Output

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.

Examples
Input
4
11
239
401
9001
Output
4
28
61
2834
Note

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

题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 2604 题。保留原作者与原赛事署名。