Problem: 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   
    

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:64000000")
using namespace std;
const double pi = 3.1415926535897932384626433832795;
double eps = 1e-9;
char ch[1 << 20];
inline string gs() {
  scanf("%s", ch);
  return string(ch);
}
inline string gl() {
  gets(ch);
  return string(ch);
}
inline int gi() {
  int x;
  scanf("%d", &x);
  return x;
}
void error(bool x) {
  if (x) {
    fprintf(stderr, "ERROR\n");
    int ttt = 0;
    cout << 7 / ttt;
  }
}
template <class T>
T gcd(T a, T b) {
  return (!a) ? b : gcd(b % a, a);
}
int mod = 1000000007;
inline int ADD(int a, int b) { return (a + b >= mod) ? a + b - mod : a + b; }
inline int SUB(int a, int b) { return (a - b < 0) ? a - b + mod : a - b; }
inline int MUL(int a, int b) { return 1ll * a * b % mod; }
inline int POW(int a, int n) {
  int r = 1;
  while (n) {
    if (n & 1) r = MUL(r, a);
    n >>= 1;
    a = MUL(a, a);
  }
  return r;
}
const int MATRIX_SIZE = 11;
typedef int matrix[MATRIX_SIZE][MATRIX_SIZE];
void MMUL(matrix &a, matrix &b) {
  matrix c;
  for (int i = (0), _b(MATRIX_SIZE); i < _b; ++i)
    for (int j = (0), _b(MATRIX_SIZE); j < _b; ++j) c[i][j] = 0;
  for (int i = (0), _b(MATRIX_SIZE); i < _b; ++i)
    for (int j = (0), _b(MATRIX_SIZE); j < _b; ++j) {
      for (int k = (0), _b(MATRIX_SIZE); k < _b; ++k)
        c[i][j] = ADD(c[i][j], MUL(a[i][k], b[k][j]));
    }
  for (int i = (0), _b(MATRIX_SIZE); i < _b; ++i)
    for (int j = (0), _b(MATRIX_SIZE); j < _b; ++j) a[i][j] = c[i][j];
}
int isp(int x) {
  if (x < 2) return 0;
  for (int d = 2; d * d <= x; ++d) {
    if (x % d == 0) return 0;
  }
  return 1;
}
int P2[10];
int waspre2 = 0;
void pre2() {
  if (waspre2) return;
  memset(P2, 0, sizeof(P2));
  waspre2 = 1;
  for (int i = (2), _b(100); i < _b; ++i) {
    if (isp(i)) ++P2[i / 10];
  }
}
int solve2(int X) {
  pre2();
  return P2[X % 10];
}
int waspre3 = 0;
vector<int> P3_1[10];
int P3_2[10][10];
void pre3() {
  if (waspre3) return;
  memset(P3_2, 0, sizeof(P3_2));
  waspre3 = 1;
  for (int i = (2), _b(1000); i < _b; ++i) {
    if (isp(i)) {
      P3_1[i / 100].push_back(i);
      ++P3_2[i / 100][i % 10];
    }
  }
}
int solve3(int X) {
  pre3();
  int res = 0;
  int a = (X / 100) % 10;
  int b = (X / 10) % 10;
  int c = (X) % 10;
  for (int i = (0), _b(P3_1[c].size()); i < _b; ++i) {
    int v = P3_1[c][i];
    int b2 = (v / 10) % 10;
    res += P3_2[b][b2];
  }
  return res;
}
int waspre4 = 0;
vector<int> P4_1[10];
vector<int> P4_2[10][10];
int P4_3[100][10];
void pre4() {
  if (waspre4) return;
  memset(P4_3, 0, sizeof(P4_3));
  waspre4 = 1;
  for (int i = (2), _b(10000); i < _b; ++i) {
    if (isp(i)) {
      P4_1[i / 1000].push_back(i);
      P4_2[i / 1000][i % 10].push_back(i);
      ++P4_3[i / 100][i % 10];
    }
  }
}
int solve4(int X) {
  pre4();
  int res = 0;
  int a = (X / 1000) % 10;
  int b = (X / 100) % 10;
  int c = (X / 10) % 10;
  int d = (X) % 10;
  for (int i = (0), _b(P4_1[d].size()); i < _b; ++i) {
    int e = (P4_1[d][i] / 100) % 10;
    int f = (P4_1[d][i] / 10) % 10;
    for (int j = (0), _b(P4_2[b][e].size()); j < _b; ++j) {
      int v = P4_2[b][e][j];
      int h = (v / 10) % 10;
      res += P4_3[c * 10 + h][f];
    }
  }
  return res;
}
int waspre5 = 0;
vector<int> P5_1[10];
vector<int> P5_2[10][10];
vector<int> P5_3[100][10];
int P5_4[1000][10];
void pre5() {
  if (waspre5) return;
  memset(P5_4, 0, sizeof(P5_4));
  waspre5 = 1;
  for (int i = (2), _b(100000); i < _b; ++i) {
    if (isp(i)) {
      P5_1[i / 10000].push_back(i);
      P5_2[i / 10000][i % 10].push_back(i);
      P5_3[i / 1000][i % 10].push_back(i);
      ++P5_4[i / 100][i % 10];
    }
  }
}
long long solve5(int X) {
  pre5();
  long long res = 0;
  int a = (X / 10000) % 10;
  int b = (X / 1000) % 10;
  int c = (X / 100) % 10;
  int d = (X / 10) % 10;
  int e = (X) % 10;
  for (int i = (0), _b(P5_1[e].size()); i < _b; ++i) {
    int f = (P5_1[e][i] / 1000) % 10;
    int g = (P5_1[e][i] / 100) % 10;
    int h = (P5_1[e][i] / 10) % 10;
    for (int j = (0), _b(P5_2[b][f].size()); j < _b; ++j) {
      int v = P5_2[b][f][j];
      int y = (v / 100) % 10;
      int z = (v / 10) % 10;
      for (int k = (0), _b(P5_3[c * 10 + y][g].size()); k < _b; ++k) {
        int vv = P5_3[c * 10 + y][g][k];
        int s = (vv / 10) % 10;
        res += P5_4[d * 100 + z * 10 + s][h];
      }
    }
  }
  return res;
}
int solve(int X) {
  int res = 0;
  if (X >= 10000)
    res = solve5(X);
  else if (X >= 1000)
    res = solve4(X);
  else if (X >= 100)
    res = solve3(X);
  else if (X >= 10)
    res = solve2(X);
  return res;
}
int main() {
  int t = gi();
  while (t--) {
    int X = gi();
    assert(isp(X));
    cout << solve(X) << endl;
  }
  return 0;
}