Problem: You are given two positive integers a and b. There are two possible operations: 

  1. multiply one of the numbers by some prime p; 
  2. divide one of the numbers on its prime factor p. 



What is the minimum number of operations required to obtain two integers having the same number of divisors? You are given several such pairs, you need to find the answer for each of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 10^5) — the number of pairs of integers for which you are to find the answer.

Each of the next t lines contain two integers a_i and b_i (1 ≤ a_i, b_i ≤ 10^6).

Output

Output t lines — the i-th of them should contain the answer for the pair a_i, b_i.

Example

Input

8
9 10
100 17
220 70
17 19
4 18
32 20
100 32
224 385


Output

1
3
1
0
1
0
1
1

Note

These are the numbers with equal number of divisors, which are optimal to obtain in the sample test case: 

  * (27, 10), 4 divisors 
  * (100, 1156), 9 divisors 
  * (220, 140), 12 divisors 
  * (17, 19), 2 divisors 
  * (12, 18), 6 divisors 
  * (50, 32), 6 divisors 
  * (224, 1925), 12 divisors 



Note that there can be several optimal pairs of numbers.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
void qmax(int &x, int y) {
  if (x < y) x = y;
}
void qmin(int &x, int y) {
  if (x > y) x = y;
}
inline int read() {
  char s;
  int k = 0, base = 1;
  while ((s = getchar()) != '-' && s != EOF && !(isdigit(s)))
    ;
  if (s == EOF) exit(0);
  if (s == '-') base = -1, s = getchar();
  while (isdigit(s)) k = k * 10 + (s ^ '0'), s = getchar();
  return k * base;
}
inline void write(long long x) {
  static char cnt, num[20];
  cnt = 0;
  if (!x) {
    putchar('0');
    return;
  }
  for (; x; x /= 10) num[++cnt] = x % 10;
  for (; cnt; putchar(num[cnt--] + 48))
    ;
}
const int Map[289][7] = {
    {0, 0, 0, 0, 0, 0, 0},  {1, 0, 0, 0, 0, 0, 0},  {1, 1, 0, 0, 0, 0, 0},
    {1, 1, 1, 0, 0, 0, 0},  {1, 1, 1, 1, 0, 0, 0},  {1, 1, 1, 1, 1, 0, 0},
    {1, 1, 1, 1, 1, 1, 0},  {1, 1, 1, 1, 1, 1, 1},  {2, 0, 0, 0, 0, 0, 0},
    {2, 1, 0, 0, 0, 0, 0},  {2, 1, 1, 0, 0, 0, 0},  {2, 1, 1, 1, 0, 0, 0},
    {2, 1, 1, 1, 1, 0, 0},  {2, 1, 1, 1, 1, 1, 0},  {2, 2, 0, 0, 0, 0, 0},
    {2, 2, 1, 0, 0, 0, 0},  {2, 2, 1, 1, 0, 0, 0},  {2, 2, 1, 1, 1, 0, 0},
    {2, 2, 1, 1, 1, 1, 0},  {2, 2, 2, 0, 0, 0, 0},  {2, 2, 2, 1, 0, 0, 0},
    {2, 2, 2, 1, 1, 0, 0},  {2, 2, 2, 1, 1, 1, 0},  {2, 2, 2, 2, 0, 0, 0},
    {2, 2, 2, 2, 1, 0, 0},  {3, 0, 0, 0, 0, 0, 0},  {3, 1, 0, 0, 0, 0, 0},
    {3, 1, 1, 0, 0, 0, 0},  {3, 1, 1, 1, 0, 0, 0},  {3, 1, 1, 1, 1, 0, 0},
    {3, 1, 1, 1, 1, 1, 0},  {3, 2, 0, 0, 0, 0, 0},  {3, 2, 1, 0, 0, 0, 0},
    {3, 2, 1, 1, 0, 0, 0},  {3, 2, 1, 1, 1, 0, 0},  {3, 2, 1, 1, 1, 1, 0},
    {3, 2, 2, 0, 0, 0, 0},  {3, 2, 2, 1, 0, 0, 0},  {3, 2, 2, 1, 1, 0, 0},
    {3, 2, 2, 2, 0, 0, 0},  {3, 2, 2, 2, 1, 0, 0},  {3, 3, 0, 0, 0, 0, 0},
    {3, 3, 1, 0, 0, 0, 0},  {3, 3, 1, 1, 0, 0, 0},  {3, 3, 1, 1, 1, 0, 0},
    {3, 3, 2, 0, 0, 0, 0},  {3, 3, 2, 1, 0, 0, 0},  {3, 3, 2, 1, 1, 0, 0},
    {3, 3, 2, 2, 0, 0, 0},  {3, 3, 3, 0, 0, 0, 0},  {3, 3, 3, 1, 0, 0, 0},
    {4, 0, 0, 0, 0, 0, 0},  {4, 1, 0, 0, 0, 0, 0},  {4, 1, 1, 0, 0, 0, 0},
    {4, 1, 1, 1, 0, 0, 0},  {4, 1, 1, 1, 1, 0, 0},  {4, 1, 1, 1, 1, 1, 0},
    {4, 2, 0, 0, 0, 0, 0},  {4, 2, 1, 0, 0, 0, 0},  {4, 2, 1, 1, 0, 0, 0},
    {4, 2, 1, 1, 1, 0, 0},  {4, 2, 1, 1, 1, 1, 0},  {4, 2, 2, 0, 0, 0, 0},
    {4, 2, 2, 1, 0, 0, 0},  {4, 2, 2, 1, 1, 0, 0},  {4, 2, 2, 2, 0, 0, 0},
    {4, 3, 0, 0, 0, 0, 0},  {4, 3, 1, 0, 0, 0, 0},  {4, 3, 1, 1, 0, 0, 0},
    {4, 3, 1, 1, 1, 0, 0},  {4, 3, 2, 0, 0, 0, 0},  {4, 3, 2, 1, 0, 0, 0},
    {4, 3, 2, 1, 1, 0, 0},  {4, 3, 2, 2, 0, 0, 0},  {4, 3, 3, 0, 0, 0, 0},
    {4, 3, 3, 1, 0, 0, 0},  {4, 4, 0, 0, 0, 0, 0},  {4, 4, 1, 0, 0, 0, 0},
    {4, 4, 1, 1, 0, 0, 0},  {4, 4, 1, 1, 1, 0, 0},  {4, 4, 2, 0, 0, 0, 0},
    {4, 4, 2, 1, 0, 0, 0},  {4, 4, 3, 0, 0, 0, 0},  {4, 4, 4, 0, 0, 0, 0},
    {5, 0, 0, 0, 0, 0, 0},  {5, 1, 0, 0, 0, 0, 0},  {5, 1, 1, 0, 0, 0, 0},
    {5, 1, 1, 1, 0, 0, 0},  {5, 1, 1, 1, 1, 0, 0},  {5, 1, 1, 1, 1, 1, 0},
    {5, 2, 0, 0, 0, 0, 0},  {5, 2, 1, 0, 0, 0, 0},  {5, 2, 1, 1, 0, 0, 0},
    {5, 2, 1, 1, 1, 0, 0},  {5, 2, 2, 0, 0, 0, 0},  {5, 2, 2, 1, 0, 0, 0},
    {5, 2, 2, 1, 1, 0, 0},  {5, 2, 2, 2, 0, 0, 0},  {5, 3, 0, 0, 0, 0, 0},
    {5, 3, 1, 0, 0, 0, 0},  {5, 3, 1, 1, 0, 0, 0},  {5, 3, 1, 1, 1, 0, 0},
    {5, 3, 2, 0, 0, 0, 0},  {5, 3, 2, 1, 0, 0, 0},  {5, 3, 3, 0, 0, 0, 0},
    {5, 3, 3, 1, 0, 0, 0},  {5, 4, 0, 0, 0, 0, 0},  {5, 4, 1, 0, 0, 0, 0},
    {5, 4, 1, 1, 0, 0, 0},  {5, 4, 1, 1, 1, 0, 0},  {5, 4, 2, 0, 0, 0, 0},
    {5, 4, 2, 1, 0, 0, 0},  {5, 4, 3, 0, 0, 0, 0},  {5, 5, 0, 0, 0, 0, 0},
    {5, 5, 1, 0, 0, 0, 0},  {5, 5, 1, 1, 0, 0, 0},  {5, 5, 2, 0, 0, 0, 0},
    {5, 5, 3, 0, 0, 0, 0},  {6, 0, 0, 0, 0, 0, 0},  {6, 1, 0, 0, 0, 0, 0},
    {6, 1, 1, 0, 0, 0, 0},  {6, 1, 1, 1, 0, 0, 0},  {6, 1, 1, 1, 1, 0, 0},
    {6, 1, 1, 1, 1, 1, 0},  {6, 2, 0, 0, 0, 0, 0},  {6, 2, 1, 0, 0, 0, 0},
    {6, 2, 1, 1, 0, 0, 0},  {6, 2, 1, 1, 1, 0, 0},  {6, 2, 2, 0, 0, 0, 0},
    {6, 2, 2, 1, 0, 0, 0},  {6, 2, 2, 2, 0, 0, 0},  {6, 3, 0, 0, 0, 0, 0},
    {6, 3, 1, 0, 0, 0, 0},  {6, 3, 1, 1, 0, 0, 0},  {6, 3, 1, 1, 1, 0, 0},
    {6, 3, 2, 0, 0, 0, 0},  {6, 3, 2, 1, 0, 0, 0},  {6, 3, 3, 0, 0, 0, 0},
    {6, 4, 0, 0, 0, 0, 0},  {6, 4, 1, 0, 0, 0, 0},  {6, 4, 1, 1, 0, 0, 0},
    {6, 4, 2, 0, 0, 0, 0},  {6, 4, 2, 1, 0, 0, 0},  {6, 4, 3, 0, 0, 0, 0},
    {6, 5, 0, 0, 0, 0, 0},  {6, 5, 1, 0, 0, 0, 0},  {6, 5, 1, 1, 0, 0, 0},
    {6, 5, 2, 0, 0, 0, 0},  {6, 6, 0, 0, 0, 0, 0},  {6, 6, 1, 0, 0, 0, 0},
    {7, 0, 0, 0, 0, 0, 0},  {7, 1, 0, 0, 0, 0, 0},  {7, 1, 1, 0, 0, 0, 0},
    {7, 1, 1, 1, 0, 0, 0},  {7, 1, 1, 1, 1, 0, 0},  {7, 2, 0, 0, 0, 0, 0},
    {7, 2, 1, 0, 0, 0, 0},  {7, 2, 1, 1, 0, 0, 0},  {7, 2, 1, 1, 1, 0, 0},
    {7, 2, 2, 0, 0, 0, 0},  {7, 2, 2, 1, 0, 0, 0},  {7, 3, 0, 0, 0, 0, 0},
    {7, 3, 1, 0, 0, 0, 0},  {7, 3, 1, 1, 0, 0, 0},  {7, 3, 2, 0, 0, 0, 0},
    {7, 3, 2, 1, 0, 0, 0},  {7, 3, 3, 0, 0, 0, 0},  {7, 4, 0, 0, 0, 0, 0},
    {7, 4, 1, 0, 0, 0, 0},  {7, 4, 1, 1, 0, 0, 0},  {7, 4, 2, 0, 0, 0, 0},
    {7, 5, 0, 0, 0, 0, 0},  {7, 5, 1, 0, 0, 0, 0},  {7, 5, 2, 0, 0, 0, 0},
    {7, 6, 0, 0, 0, 0, 0},  {7, 6, 1, 0, 0, 0, 0},  {7, 7, 0, 0, 0, 0, 0},
    {8, 0, 0, 0, 0, 0, 0},  {8, 1, 0, 0, 0, 0, 0},  {8, 1, 1, 0, 0, 0, 0},
    {8, 1, 1, 1, 0, 0, 0},  {8, 1, 1, 1, 1, 0, 0},  {8, 2, 0, 0, 0, 0, 0},
    {8, 2, 1, 0, 0, 0, 0},  {8, 2, 1, 1, 0, 0, 0},  {8, 2, 1, 1, 1, 0, 0},
    {8, 2, 2, 0, 0, 0, 0},  {8, 2, 2, 1, 0, 0, 0},  {8, 3, 0, 0, 0, 0, 0},
    {8, 3, 1, 0, 0, 0, 0},  {8, 3, 1, 1, 0, 0, 0},  {8, 3, 2, 0, 0, 0, 0},
    {8, 3, 3, 0, 0, 0, 0},  {8, 4, 0, 0, 0, 0, 0},  {8, 4, 1, 0, 0, 0, 0},
    {8, 4, 1, 1, 0, 0, 0},  {8, 4, 2, 0, 0, 0, 0},  {8, 5, 0, 0, 0, 0, 0},
    {8, 5, 1, 0, 0, 0, 0},  {8, 6, 0, 0, 0, 0, 0},  {8, 6, 1, 0, 0, 0, 0},
    {8, 7, 0, 0, 0, 0, 0},  {9, 0, 0, 0, 0, 0, 0},  {9, 1, 0, 0, 0, 0, 0},
    {9, 1, 1, 0, 0, 0, 0},  {9, 1, 1, 1, 0, 0, 0},  {9, 1, 1, 1, 1, 0, 0},
    {9, 2, 0, 0, 0, 0, 0},  {9, 2, 1, 0, 0, 0, 0},  {9, 2, 1, 1, 0, 0, 0},
    {9, 2, 2, 0, 0, 0, 0},  {9, 2, 2, 1, 0, 0, 0},  {9, 3, 0, 0, 0, 0, 0},
    {9, 3, 1, 0, 0, 0, 0},  {9, 3, 1, 1, 0, 0, 0},  {9, 3, 2, 0, 0, 0, 0},
    {9, 4, 0, 0, 0, 0, 0},  {9, 4, 1, 0, 0, 0, 0},  {9, 5, 0, 0, 0, 0, 0},
    {9, 5, 1, 0, 0, 0, 0},  {9, 6, 0, 0, 0, 0, 0},  {10, 0, 0, 0, 0, 0, 0},
    {10, 1, 0, 0, 0, 0, 0}, {10, 1, 1, 0, 0, 0, 0}, {10, 1, 1, 1, 0, 0, 0},
    {10, 2, 0, 0, 0, 0, 0}, {10, 2, 1, 0, 0, 0, 0}, {10, 2, 1, 1, 0, 0, 0},
    {10, 2, 2, 0, 0, 0, 0}, {10, 3, 0, 0, 0, 0, 0}, {10, 3, 1, 0, 0, 0, 0},
    {10, 3, 1, 1, 0, 0, 0}, {10, 3, 2, 0, 0, 0, 0}, {10, 4, 0, 0, 0, 0, 0},
    {10, 4, 1, 0, 0, 0, 0}, {10, 5, 0, 0, 0, 0, 0}, {10, 6, 0, 0, 0, 0, 0},
    {11, 0, 0, 0, 0, 0, 0}, {11, 1, 0, 0, 0, 0, 0}, {11, 1, 1, 0, 0, 0, 0},
    {11, 1, 1, 1, 0, 0, 0}, {11, 2, 0, 0, 0, 0, 0}, {11, 2, 1, 0, 0, 0, 0},
    {11, 2, 1, 1, 0, 0, 0}, {11, 2, 2, 0, 0, 0, 0}, {11, 3, 0, 0, 0, 0, 0},
    {11, 3, 1, 0, 0, 0, 0}, {11, 4, 0, 0, 0, 0, 0}, {11, 4, 1, 0, 0, 0, 0},
    {11, 5, 0, 0, 0, 0, 0}, {12, 0, 0, 0, 0, 0, 0}, {12, 1, 0, 0, 0, 0, 0},
    {12, 1, 1, 0, 0, 0, 0}, {12, 1, 1, 1, 0, 0, 0}, {12, 2, 0, 0, 0, 0, 0},
    {12, 2, 1, 0, 0, 0, 0}, {12, 2, 2, 0, 0, 0, 0}, {12, 3, 0, 0, 0, 0, 0},
    {12, 3, 1, 0, 0, 0, 0}, {12, 4, 0, 0, 0, 0, 0}, {12, 5, 0, 0, 0, 0, 0},
    {13, 0, 0, 0, 0, 0, 0}, {13, 1, 0, 0, 0, 0, 0}, {13, 1, 1, 0, 0, 0, 0},
    {13, 1, 1, 1, 0, 0, 0}, {13, 2, 0, 0, 0, 0, 0}, {13, 2, 1, 0, 0, 0, 0},
    {13, 3, 0, 0, 0, 0, 0}, {13, 4, 0, 0, 0, 0, 0}, {14, 0, 0, 0, 0, 0, 0},
    {14, 1, 0, 0, 0, 0, 0}, {14, 1, 1, 0, 0, 0, 0}, {14, 2, 0, 0, 0, 0, 0},
    {14, 2, 1, 0, 0, 0, 0}, {14, 3, 0, 0, 0, 0, 0}, {15, 0, 0, 0, 0, 0, 0},
    {15, 1, 0, 0, 0, 0, 0}, {15, 1, 1, 0, 0, 0, 0}, {15, 2, 0, 0, 0, 0, 0},
    {15, 3, 0, 0, 0, 0, 0}, {16, 0, 0, 0, 0, 0, 0}, {16, 1, 0, 0, 0, 0, 0},
    {16, 1, 1, 0, 0, 0, 0}, {16, 2, 0, 0, 0, 0, 0}, {17, 0, 0, 0, 0, 0, 0},
    {17, 1, 0, 0, 0, 0, 0}, {18, 0, 0, 0, 0, 0, 0}, {18, 1, 0, 0, 0, 0, 0},
    {19, 0, 0, 0, 0, 0, 0}};
const string dis[289] = {
    "0",
    "10",
    "210",
    "3210",
    "43210",
    "543210",
    "6543210",
    "76543210",
    "211234560",
    "3211234510",
    "43211234210",
    "543211233210",
    "6543211243210",
    "76543211543210",
    "432223452112340",
    "5432223432112310",
    "65432223432112210",
    "765432225432113210",
    "8765432265432143210",
    "65433334432223211230",
    "765433335432223211210",
    "8765433365432243211210",
    "98765433765432543213210",
    "876544446543334322221120",
    "9876544476543354322321110",
    "21012345112345234564567670",
    "321012342112342234534565610",
    "4321012332112322234334545210",
    "54321012432112322233334443210",
    "654321015432114322233334443210",
    "7654321065432154322433344543210",
    "43211234210123112342345452112340",
    "543211233210122112322343432112310",
    "6543211243210132112222333432112210",
    "76543211543210432113222335432113210",
    "876543216543215432143223365432143210",
    "6543222343211221012112323432223211230",
    "76543222543211321012112225432223211210",
    "876543226543214321032112265432243211210",
    "8765433365432243211210111654333432222110",
    "98765433765432543213210217654335432232110",
    "432101233211232223433454521012311234234450",
    "5432101243211232223333444321012211232233410",
    "65432101543211432223333444321013211222233210",
    "765432106543215432243334454321043211322333210",
    "6543211243210132112222333432112210121122321120",
    "76543211543210432113222335432113210121122321110",
    "876543216543215432143223365432143210321224321210",
    "8765432265432143210321122654322432112101143222110",
    "65432101543211432223333444321013211222233210111220",
    "765432106543215432243334454321043211322333210211210",
    "3212345621234523456456767123456234564566734564566560",
    "43212345321234223453456562123451234534556234534554510",
    "543212344321233223433454532123421234234451234234434210",
    "6543212354321243223333444432123321232233421231233233210",
    "76543212654321543224333445432124321232233321221221243210",
    "876543217654326543254334465432154321432334321321221543210",
    "5432234532123421234234545322345123452344523453454452112340",
    "65432234432123321232234344322342123412334223423433432112310",
    "765432235432124321232233354322332123212233223123223432112210",
    "8765432265432154321432233654322432123212243222121225432113210",
    "98765432765432654325432437654325432143232543232123265432143210",
    "765433345432233212321232354333432234123233334234334432223211230",
    "8765433365432243212321222654333432232121243332232335432223211210",
    "98765433765432543214321327654335432232121543332213365432243211210",
    "987654447654335432232122176544454333322125444333244654333432222110",
    "5432123443212332234334545321234212342344512342344342101231123423440",
    "65432123543212432233334444321233212322334212312332332101221123223310",
    "765432126543215432243334454321243212322333212212212432101321122223210",
    "8765432176543265432543344654321543214323343213212215432104321132233210",
    "76543223543212432123223335432233212321223322312322343211221012112221120",
    "876543226543215432143223365432243212321224322212122543211321012112321110",
    "9876543276543265432543243765432543214323254323212326543214321032124321210",
    "9876543376543254321432132765433543223212154333221336543224321121014322211"
    "0",
    "76543212654321543224333445432124321232233321221221243210132112222321011122"
    "0",
    "87654321765432654325433446543215432143233432132122154321043211322332102112"
    "10",
    "65432345543234432343345454323453234523445234534544532123421234234412342344"
    "340",
    "76543234654323543234334445432344323432334323423433443212332123223321231233"
    "2310",
    "87654323765432654325433446543235432343233432332322354321243212322332122122"
    "12210",
    "98765432876543765436543547654326543254343543243233265432154321432343213212"
    "213210",
    "87654334654323543234323336543344323432323433423433454322332123212232231232"
    "2321120",
    "98765433765432654325432437654335432343232543332323365432243212321243222121"
    "22321110",
    "87654323765432654325433446543235432343233432332322354321243212322332122122"
    "122101110",
    "98765434876543765436543547654346543454343543443433465432354323432343233232"
    "2332122110",
    "32123456101234123453456562123451234534556234534554512345623456456634564566"
    "56456756670",
    "43212345210123112342345452112340123423445123423443421234512345345523453455"
    "453456455610",
    "54321234321012211232234343211231012312334212312332332123421234234412342344"
    "3423453445210",
    "65432123432101321122223334321122101211223211201221243212332123223321231233"
    "23323423343210",
    "76543212543210432113222335432113210121122321110112154321243212322332122122"
    "124323322343210",
    "87654321654321543214322336543214321032122432121012165432154321432343213212"
    "2154324334543210",
    "54322345321123101231234343222341123412334223423433432234512345234423453454"
    "45345645562112340",
    "65432234432112210121123234322232112301223322312322343223421234123322342343"
    "342345344532112310",
    "76543223543211321012112225432223211210112322211212254322332123212232231232"
    "2332342334432112210",
    "87654322654321432103211226543224321121011432221103265432243212321243222121"
    "22432332235432113210",
    "76543334543222321121012125433333222311212433322323354333432234123233342343"
    "343345344543222321120",
    "87654333654322432112101116543334322221101433322213365433343223212143332232"
    "3343342334543222321110",
    "98765433765432543213210217654335432232110543332214376543354322321254333221"
    "33543332336543224321210",
    "98765444765433543223211107654445433332211544433324476544454333322154443332"
    "445444334465433343222110",
    "54321234321012211232234343211231012312334212312332332123421234234412342344"
    "3423453445210123112323440",
    "65432123432101321122223334321122101211223211201221243212332123223321231233"
    "23323423343210122112223310",
    "76543212543210432113222335432113210121122321110112154321243212322332122122"
    "124323322343210132112223210",
    "87654321654321543214322336543214321032122432121012165432154321432343213212"
    "2154324334543210432132233210",
    "76543223543211321012112225432223211210112322211212254322332123212232231232"
    "23323423344321122101112221120",
    "87654322654321432103211226543224321121011432221103265432243212321243222121"
    "224323322354321132102112321110",
    "76543212543210432113222335432113210121122321110112154321243212322332122122"
    "1243233223432101321122232101110",
    "87654321654321543214322336543214321032122432121012165432154321432343213212"
    "21543243345432104321322332102110",
    "65432345432123321232234344322342123412334323423433432123410123123321231233"
    "231234233432123421232344123423340",
    "76543234543212432123223335432233212321223322312322343212321012112221120122"
    "1221231223432123321222332123122310",
    "87654323654321543214322336543224321232122432221213254321232101211232111011"
    "21321221125432124321322332122112210",
    "98765432765432654325432437654325432143232543232123265432143210321243212101"
    "214321322365432154324323432132213210",
    "87654334654322432123212226543334322321212433322323354322332112101132221121"
    "2232231223543223321221223223122321120",
    "98765433765432543214321327654335432232121543332214365432243211210143222110"
    "32432221226543224321321243222122321110",
    "87654323654321543214322336543224321232122432221213254321232101211232111011"
    "213212211254321243213223321221122101110",
    "65432345432123210121123234322342112301223322312322343234521234123332342343"
    "3423453445321234101212332123122312342330",
    "76543234543212321012112225432233211210112432221213254323432123212232231232"
    "23323423344321232101112221120112212312210",
    "87654323654321432103211226543224321121011432221103265432343212321243222121"
    "324323322354321232102112321110213212211210",
    "87654334654322432112101116543334322221101543332214365433443223212143332232"
    "3343342334543223321110113222112232231222110",
    "87654323654321432103211226543224321121011432221103265432343212321243222121"
    "32432332235432123210211232111021321221121010",
    "43212345212345234564567672123452345645667234545664522345634567567734565677"
    "564567676712345634565677345656564567676456660",
    "54321234321234223453456563212341234534556123434553432234523456456623454566"
    "4534565656212345234545662345454534565653455510",
    "65432123432123322343345454321232123423445212323442343223432345345522343455"
    "34334545453212342234345512343434234545423444210",
    "76543212543212432233334445432123212322334321212331254322343234334432232344"
    "234334343443212332233344212323233234343323333210",
    "87654321654321543224333446543214321232233432121222165432254323433443223233"
    "2254334334543212432233343212221243233324323243210",
    "98765432765432654325433447654325432143233543232123276543265432543454324323"
    "32654354456543215432433443213221543243354343543210",
    "65432234432123212342345454322342123423445223423443443234522345345523453455"
    "453456455632123412343455123434342345454234442112340",
    "76543223543212321232234345432233212312334322312332354323432234234432342344"
    "3433453445432123212323442123232322343431233332112310",
    "87654322654321432123223336543224321221223432221222265432343223323343232233"
    "23433433345432123212223332121212322323221222432112210",
    "98765432765432543214322337654325432132122543232113276543254322432354323222"
    "325433433465432143213223432121214322322321215432113210",
    "87654333654322432122123236543334322321223433322323365433443234223343342343"
    "3443453445543223321212333223122332342332122243222321120",
    "98765433765432543213212227654335432232112543332213376543354323322254333232"
    "33543433346543224321212243222122432322232111543222321110",
    ":9876544876543654324321218765446543343221654443324487654465433432265444332"
    "446544434476543354323211543332335433323432226543334322210",
    "65432123432123322343345454321232123423445212323442343223432345345522343455"
    "3433454545321234223434551234343423454542344421012311232340",
    "76543212543212432233334445432123212322334321212331254322343234334432232344"
    "23433434344321233223334421232323323434322333321012211222310",
    "87654321654321543224333446543214321232233432121222165432254323433443223233"
    "225433433454321243223334321222124323332322324321013211223210",
    "98765432765432654325433447654325432143233543232123276543265432543454324323"
    "3265435445654321543243344321322154324334323254321043213233210",
    "87654322654321432123223336543224321221223432221222265432343223323343232233"
    "23433433345432123212223332121212322323221222432112210111221120",
    "98765432765432543214322337654325432132122543232113276543254322432354323222"
    "325433433465432143213223432121214322322321215432113210212321110",
    "87654321654321543224333446543214321232233432121222165432254323433443223233"
    "2254334334543212432233343212221243233323223243210132112232101110",
    "76543234543223432343345455432343223423445323423443443212321234234421232344"
    "23223434344322343234345522343434123434323444321234212323412342330",
    "87654323654322543234334446543234322332334432322332354321232123223332121233"
    "123223232354322343233344322323232123232323334321233212223212312210",
    "98765432765432654325433447654325432243233543232223265432143212322343212122"
    "2143223223654322543243344322322232122214323254321243213233212211210",
    "98765433765432543224323337654335432332223543332323365432243212212243222122"
    "22432322236543234322323343232223321212132222543223321221232231222110",
    ":9876543876543654325432438765436543243232654343224376543254321321254323211"
    "325432323376543254324323543232324321212432326543224321322432221232110",
    "98765432765432654325433447654325432243233543232223265432143212322343212122"
    "2143223223654322543243344322322232122214323254321243213233212211210110",
    "76543234543212321232234345432233212312334322312332354323432234234432342344"
    "34334534454321232123234421232323223434312333321234101212321231221232330",
    "87654323654321432123223336543224321221223432221223265432343223323343232233"
    "234334333454321232122233321212123223232212224321232101112211201121212210",
    "98765432765432543214322337654325432132122543232113276543254322432354323222"
    "3254334334654321432132234321212143223223212154321232102123211102321211210",
    "98765433765432543213212227654335432232112543332214376543354323322254333232"
    "3354343334654322432121224322212243232223211154322332111013222112322122211"
    "0",
    "87654323654323432343345456543234323423445432323442365433443345345543343455"
    "34444545455432343234345532343434334545423444432123212323421232322233431233"
    "0",
    "98765432765432543234334447654325432332334543232333276543354334434454333344"
    "33544444456543234323334443232323433434332333543212321222332121213222322122"
    "10",
    "32101234211234123453456561012341234534556123434553421234523456456623454566"
    "45345656562223452345456623454545345656534555123456345656734565654566764566"
    "560",
    "43210123321123212342345452101231123423445012323442332123422345345512343455"
    "34234545453212341234345512343434234545423444212345234545623454543455653455"
    "4510",
    "54321012432112321232234343210122112312334101212331243212332234234421232344"
    "23323434344321232123234421232323223434312333321234223434512343432344542344"
    "34210",
    "65432101543211432123223334321013211221223210111220154321243223323332122233"
    "12432333235432123212223332121212322323221222432123322323421232323233433233"
    "233210",
    "76543210654321543214322335432104321132122321021111065432154322432343213222"
    "21543243346543214321322343212121432232232121543212432232332122214323324322"
    "3243210",
    "54321123321012211231234343211231012312334112312332332123421234234412342344"
    "34234534452101231123234401232323123434322333321234123434512343432344542344"
    "34211230",
    "65432112432101321122123234321122101211223211201221243212332123223321231233"
    "23323423343210122112123310121212212323221222432123212323421232322233431233"
    "233211210",
    "76543211543210432113212225432113210121112321110111154321243212322232122122"
    "12432332234321013211212221011101321222132111543212321222332121213222322122"
    "3243211210",
    "87654321654321543214321326543214321032121432121012165432154321432343213212"
    "21543243345432104321321232102110432132243222654321432132243212124323223212"
    "43543213210",
    "76543222543211321012112125432223211210112322211212254322332123212232231232"
    "23323423344321122101112221120112212312210111543223321212332231223232332122"
    "324321221120",
    "87654322654321432103211216543224321121011432221102265432243212321243222121"
    "22432332235432113210211132111011321221121010654322432121243222124322223211"
    "4354321321110",
    "54321012432112321232234343210122112312334101212331243212332234234421232344"
    "23323434343212232123234412232323233434312333321234223434512343432344542344"
    "34210121123230",
    "65432101543211432123223334321013211221223210111220154321243223323332122233"
    "12432333234321123212223321121212322323221222432123322323421232323233432233"
    "233210121121210",
    "76543210654321543214322335432104321132122321021111065432154322432343213222"
    "21543243345432114321322332112111432232232121543212432232332122214323323222"
    "3243210321121210",
    "76543211543210432113212225432113210121112321110111154321243212322232122122"
    "12432332234321013211212221011101321222121212543212321222332121213222322122"
    "32432112101112110",
    "87654321654321543214321326543214321032121432121012165432154321432343213212"
    "21543243345432104321321232102110432132232121654321432132243212124323223212"
    "435432132102132110",
    "76543210654321543214322335432104321132122321021111065432154322432343213222"
    "21543243345432124321322332122112432332232121543212432232332122214323323222"
    "3243210321121210110",
    "65432123543212432233234344321233212322334212312332332101221123123310121233"
    "12212323234321233223234421232323222323223333432234323434522343431233432344"
    "34321232123231232330",
    "76543212654321543224323335432124321232223321221221243210132112212221011122"
    "01321222125432124322323332122212321212132222543223432333432232322122323233"
    "334321232122221212210",
    "87654321765432654325432436543215432143232432132122154321043211321232102111"
    "10432132236543215432432343213221432121243232654322543243343223223212214323"
    "4354321432132321211210",
    "87654322654321543214322326543224321232122432221212254321132101211132111011"
    "11321221125432124321322232122112210111032121654323432232343232223211213222"
    "43543223212213221222110",
    "65432123432101321122123234321122101211223211201221243212332123223321231233"
    "23323423343210122112123310121212212323222222432123212323421232322233431233"
    "233212310121221212212320",
    "76543212543210432113212225432113210121112321110112154321243212322232122122"
    "12432332234321013211212221011101321222132111543212321222332121213222322122"
    "3243212210111211011212110",
    "87654322654321432103211216543224321121011432221103265432243212321243222121"
    "22432332235432113210211132111011321221121010654322432121243222124322223211"
    "43543213211103211113221210",
    "76543212543212432233234345432123212322334321212331254322343234334432232344"
    "23433434344321233223234421232323323434332333321012211212310121212122322222"
    "124321221232321223222331230",
    "87654321654321543224323336543214321232223432121222165432254323433343223233"
    "22543343345432124322323332122212432333243222432101321121221011103212213211"
    "2154321321222321121322221210",
    "65432101543211432123223234321013211221223210111220154321243223323332122233"
    "12432333235432223212223332221222323323321222432123322323421232323233433233"
    "23321012112121011212122222120",
    "43212345212345012342345452123451234523445234534544521234523456345523454565"
    "45345656563234561234345523453445345645523444234567234545634564554565663455"
    "451234534563434545534554545640",
    "54321234321234101231234343212342123412334123423433432123412345234412343454"
    "34234545452123450123234412342334234534412333323456123434523453443454552344"
    "3421234234523234344234434345310",
    "65432123432123210121123234321232112301223212312322343212321234123321232343"
    "23223434343212341012123321231223123423301222432345212323422342332343441233"
    "23321232234121232331233232342210",
    "76543212543212321012112225432123211210112321221211254321232123212232121232"
    "12322323234321232101112221120112212312210111543234321212332231223232332122"
    "324321221230121212221223212313210",
    "87654321654321432103211226543214321121011432121102165432143212321243212121"
    "21432232235432123210211232111021321221121010654323432121243222124322223211"
    "4354321321210321211321121032243210",
    "65432234432123211230123234322342123412323223423433443223421234234322342344"
    "34234534453212341123123312342334123434312323432345223423423453442344542343"
    "34322341234232343442343233343211230",
    "76543223543212321121012125432233212311212322312322354322332123123232231233"
    "23323423344321232112012221231223212323211212543234322312332342333233432232"
    "334322321231222323322321222323211210",
    "87654322654321432112101116543224321221101432221212265432243212212143222122"
    "22432322235432123211101132121112321212121101654323432221243232224322323221"
    "4354322321211322122322121132243211210",
    "98765432765432543213210217654325432132110543232113276543254321321254323211"
    "32543232336543214321210143212121432121232111765432543232154323235433234322"
    "54654324321214322124322321433543213210",
    "87654333654322432122112016543334322321212433322323365433343223212243332232"
    "33433423345432233212112132231223322312221212654334432322243342334332333232"
    "435432332231232323332322223324321221120",
    "98765433765432543213211107654335432232111543332213376543354322321154333221"
    "33543332336543224321211043222122432221232111765433543232154333235433234322"
    "5465432432221432222432232143354321321110",
    "65432123432123210121123234321232112301223212312322343212321234123321232343"
    "23223434343212341012123321231223123423301222432345212323422342332343441233"
    "23321232234121232331233232342210121123230",
    "76543212543212321012112225432123211210112321221211254321232123212232121232"
    "12322323234321232101112221120112212312210111543234321212332231223232332122"
    "324321221230121212221222212313210121121210",
    "87654321654321432103211226543214321121011432121102165432143212321243212121"
    "21432232235432123210211232111021321221121010654323432121243222124322223211"
    "4354321321210321211321121032243210321121210",
    "87654322654321432112101116543224321221101432221212265432243212212143222122"
    "22432322235432123211101132121112321212121101654323432221243232224322323221"
    "43543223212113221223221211322432112101112110",
    "87654321654321432103211226543214321121011432121102165432143212321243212121"
    "21432232235432123210211232111021321221121010654323432121243222124322223211"
    "435432132121032121132112103224321032112121010",
    "76543234543223321232123235432343223412323323423433443212321234012221231232"
    "23212323234322342123123332342334223412212323543345323423433453442342332343"
    "3443234323423234344123323334332123212323123230",
    "87654323654322432123212226543234322321212432332322354321232123101132122121"
    "12321212125432233212212232231223212301121212654334432322343342333231223232"
    "43543233223123232332122322332432123212122121210",
    "98765432765432543214321327654325432232121543232213265432143212210143212110"
    "21432121226543224321321243222132321210232121765433543232254333234322124322"
    "546543243222143232232123214335432143212132121210",
    "98765433765432543223212217654335432332212543332323365432243212211043222121"
    "22432221226543234322212143232223321211132212765434543332254343334322224332"
    "5465433432322433233322132243354322321221322122110",
    "76543234543212321231012125432233212321212322312322354323432123123232231233"
    "23323423344321232123012221231223212323222312543234323412332342333233432342"
    "34432342123233232332342123233321231012122121212320",
    "87654323654321432122101116543224321221101432221213265432343212212143222122"
    "22432322235432123212101132122112321212121201654323432321243232224322323231"
    "435432332122232212232312123234321221011121101212110",
    "87654323654323432122123236543234322321223432322322365432343234223343232343"
    "23433434345432343212123332231223323423321222432123212301221231222122323231"
    "2354323323412323233323323212243212212323212222233120",
    "98765432765432543213212227654325432232112543232213276543254323322254323232"
    "32543333346543234321212243222122432322232111543212321210132122113211212120"
    "32654324323214322224322321213543213212223211132222110",
    "76543212543212321012112125432123211210112321221211254321232123212232121232"
    "12322323234321232101112221120112212312210111543234321212332231223232332122"
    "324321221230121212221223212313210121121210111212222120",
    "54323456322345123453456562123452345634556234545654510123412345345512343455"
    "34234545452123452345456623454545234545434555323456345656734565653455654566"
    "5623456345645345565234434545512345345656345553455455640",
    "65432345432234212342345453212342234523445123434543421012311234234401232344"
    "23123434343212341234345512343434123434323444432345234545623454542344543455"
    "45323452345342344541233234344212342345452344423443445310",
    "76543234543223321232234344321233223412334212323432332101221123223310121233"
    "12212323234321232123234421232323212323212333543234323434522343431233432344"
    "344323422342312334301221232333212322343412333123323342210",
    "87654323654322432123223335432124322321223321222321243210132112222321011122"
    "01321222125432123212223332121212321222121222654323432323432232322122323233"
    "4354323322312212232101121232243212322323212222122322313210",
    "98765432765432543214322336543215432232122432132212154321043211322332102112"
    "10432132236543214321322343212121432132232121765432543232343223223212214322"
    "54654324322213212212101321433543214322323212132124332243210",
    "76543345543234322341234344322342123423434223423443432112310123123311231233"
    "23123423344322342123234412342334012323212333543345323434523453441233432344"
    "344334523453423434412322333443223412343423434223323343211230",
    "87654334654323432232123235432233212322323322312332343211221012112221120122"
    "12212312235432233212123321231223101212121222654334432323432342332122323233"
    "4354334323423223233112122233343223212323223232122122323211210",
    "98765433765432543223212226543224321232212432221222254321132101211232111011"
    "11321221126543224321212232122112210111032111765433543232343232223211214322"
    "54654334323223221222110321433543223212223221232112132243211210",
    "98765444765433543233223126543334322321223433322323354322232112101132221121"
    "22322312236543334322212232231223211201132212765444543332343342333221224332"
    "546543443342332323321213224335432332231221222101121322432222110",
    ":9876544876543654324322217654335432232122543332213365432243211210143222110"
    "22432221227654335432321143222122321110143221876544654343254333234322125433"
    "6576543543332432222321143254465432432221321212101324335432232110",
    "76543234543223321232234344321233223412334212323432332101221123223310121233"
    "12212323234321232123234421232323122333212333543234323434522343431233432344"
    "34432342234231233430122123233321232234341233312332334221012112230",
    "87654323654322432123223335432124322321223321222321243210132112222321011122"
    "01321222125432123212223332121212211222121222654323432323432232322122323233"
    "435432332231221223210112123224321232232321222212222231321012112210",
    "98765432765432543214322336543215432232122432132212154321043211322332102112"
    "10432132236543214321322343212121321122132121765432543232343223223212214322"
    "5465432432221321221210132143354321432232321213212323224321032122210",
    "98765433765432543223212226543224321232212432221222254321132101211232111011"
    "11321221126543224321212232122112210111032111765433543232343232223211214322"
    "54654334323223221222110321433543223212223221221212132243211210112110",
    "87654345654334432343234345432344323423434323423443443212332123123321231233"
    "23101212125432343223234432342334212323222333654345433434533453442233433344"
    "445434533453423434412322333444323432343423434123323343321232122312320",
    "98765434765433543234323336543235432332323432332332354321243212212232122122"
    "12210111016543234322323343232223321212132222765434543333443343333222324333"
    "5465434433423323233212132243354323432323323232122323324321232112212110",
    "87654345654323432232123235432343212322323322312332343212321012112221120122"
    "12212312235432343212123321231223101212121222654345432323432342332122323233"
    "43543343234233342332231232343432232123233232323221223232123101122121120",
    "98765434765432543223212226543234321232212432221223254321232101211232111011"
    "21321221126543234321212232122112210111032111765434543232343232223211214322"
    "546543343232232312221203214345432232122232212321121323432122101121102110",
    "98765434765433543233234346543234323432334432323432354321232123223332121233"
    "12322323236543234323234432232323212323232333543234322312321232321011212122"
    "3265434433423323343212232323354323323434323333233231224321221223212222120",
    "54323456321234223453456563223451234534556234534554521234523456456623454566"
    "45345656562123452345456623454545345656534555323456345656734565654566764566"
    "5633456234545345455345534545523345345656345554566455641234534556345545455"
    "0",
    "65432345432123322343345454322342123423445223423443432123422345345512343455"
    "34234545453212342234345512343434234545423444432345234545623454543455653455"
    "45323451234342343442344234344322342345452344434553445321234234452344343441"
    "0",
    "76543234543212432233334445432233212322334322312332343212332234334421232344"
    "23323434344321233223334421232323323434322333543234323434532343432344542344"
    "34432342123232232331233123233432233234342233323442334232123223341233232332"
    "10",
    "87654323654321543224333446543224321232233432221222254321243223333432122233"
    "12432333235432124322333432122212432333232232654323432333443232323233433233"
    "43543233212223221222122212323543224323333222232333233243212322332122323223"
    "210",
    "76543345543223321232234345433343223412334333423433443223421234234422342344"
    "34234534454322342123234422342334123434312333543345323434533453442344542344"
    "34432342234232343442343233343321232234341233323443334232234123342343342332"
    "1120",
    "87654334654322432123223336543334322321223433322323354322332123223332231233"
    "23323423345432233212223332231223212323221222654334432323443342333233433233"
    "43543233223123232332232222332432123223232122232332223143223212232232231223"
    "21110",
    "98765433765432543214322337654335432232122543332213365432243212322343222122"
    "22432332236543224321322343222122321222132121765433543232354333234322324322"
    "54654324322214322223221321433543214322323212143223232254322321223221322134"
    "321210",
    "98765444765433543223212227654445433332212544433324465433343223212243332232"
    "33433423346543334322212243332233322312232212765444543332354443344332334332"
    "54654334323224332333232322433543223212223221221222132254333322123332322234"
    "3222110",
    "76543234543212432233334445432233212322334322312332343212332234334421232344"
    "23323434344321233223334421232323223434323343543234323434532343432344542344"
    "34432342123232232331233123233432333234342333323442334332123223341233232332"
    "10111220",
    "87654323654321543224333446543224321232233432221222254321243223333432122233"
    "12432333235432124322333432122212322333232232654323432333443232323233433233"
    "43543233212223221222122212323543224323333222232333233243212322332122322223"
    "210211210",
    "98765432765432654325433447654325432143233543232123265432154322433443213223"
    "21543243346543215432433443213221432233243232765432543243454323234323324323"
    "54654324321324322123212322433654325432434323243234343354321432333212433234"
    "3213212210",
    "98765433765432543214322337654335432232122543332213365432243212322343222122"
    "22432332236543224321322343222122321222132121765433543232354333234322324322"
    "54654324322214322223221321433543214322323212132223232254322321223221322134"
    "32121012110",
    "87654345654323543234334446543344323432334433423433454323432123223332231233"
    "23212323235432344323334432342334212323232333654345433434543453443233433344"
    "44543343234233343442342233343543233234343233323332334243234212232232121223"
    "212212212320",
    "98765434765432654325433447654335432343233543332323365432343212322343222122"
    "22321222126543235432433443233223321222143232765434543343454343334322324333"
    "54654334323324332333231322434654324323334322232223243354323321223221212134"
    "3213212212110",
    "87654345654323432123223336543344322321223433322323354323432123223332231233"
    "23323423345432343212223332231223212323221222654345432323443342333233433233"
    "43543233234123232333342332342432123223232122232332323143223212233232231223"
    "21210112121120",
    "98765434765432543234334447654335432332334543332333365432343234334443232344"
    "23433434346543234323334443232323323434332333543234321222332231222122322122"
    "32654344323234332333233323333543234334343233343443323254323323343233332314"
    "321212221222210",
    "43212345210123112342345452112340123423445123423443421234512345345523453455"
    "45345645561012341234345512343434234545423444212345234545623454543455653455"
    "45323451234342343443454234344332342345452344434553445323345345563455454551"
    "2343455345545450",
    "54321234321012211232234343211231012312334212312332332123421234234412342344"
    "34234534452101231123234401232323123434312333321234123434512343432344542344"
    "34212340123231232332343123233321231234341233323442334232234234452344343442"
    "12323442344343410",
    "65432123432101321122223334321122101211223211201221243212332123223321231233"
    "23323423343210122112223310121212212323221222432123212323421232322233431233"
    "23321231012122121221232012122432122123232122222331223143223323342233332333"
    "212223312332323210",
    "76543212543210432113222335432113210121122321110112154321243212322332122122"
    "12432332234321013211222321011101321222132121543212321222332121213222322122"
    "32432122101112110112121101213543213212223211132222132254322432333222433234"
    "3213223212232323210",
    "65432234432112210121123234322232112301223322312322343223421234123322342343"
    "34234534453211231012123311231223123423301222432234212323422342332343441233"
    "23321231123121232332343122232210121123230122212332223132123223341233232333"
    "22312332343342321120",
    "76543223543211321012112225432223211210112322211212254322332123212232231232"
    "23323423344321122101112221120112212312210111543223321212332231223232332122"
    "32432122112012121222232111221321012112121011121222112043212322232122322224"
    "322212222322312321110",
    "87654322654321432103211226543224321121011432221103265432243212321243222121"
    "22432332235432113210211232111011321221121010654322432121243222124322223211"
    "43543213211103211113221210322432103211212101032123221154321432323212433235"
    "4323212322132234321210",
    "87654333654322432112101116543334322221101433322213365433343223212143332232"
    "33433423345432223211101132221122322312221101654333432221243332234332333221"
    "43543223212113221223232211322432112101112110121211021154322321223221322135"
    "43332213332332343222110",
    "65432123432101321122223334321122101211223211201221243212332123223321231233"
    "23323423343210122112223310121212212323212232432123212323421232322233431233"
    "23321231012122121221232012122321222123231222223331223243233212232232231223"
    "212223312332323210111220",
    "76543212543210432113222335432113210121122321110112154321243212322332122122"
    "12432332234321013211222321011101321222121121543212321222332121213222322122"
    "32432122101112110112121101212432113212222111132222122154322321223221322134"
    "3213223212232223210211210",
    "76543234543212432123223335432233212321223322312322343212321012112221120122"
    "12212312234321233212223321231223101212121222543234322323432342332122322233"
    "33432232123123232332231122232432122123232122222221223132123101122121120114"
    "32321222232121232122122120",
    "87654323654321543214322336543224321232122432221213254321232101211232111011"
    "21321221125432124321322332122112210111032121654323432232343232223211213222"
    "43543223212213221222120211323543213212223211132112132243212210112110211025"
    "432321232212123432132122110",
    "76543234543212321012112225432233211210112432221213254323432123212232231232"
    "23323423344321232101112221120112212312210111543234321212332231223232332122"
    "32432122123012121223232221231321012112121011121222212043212212232122221224"
    "3222122323223123212101121120",
    "54323456321234223453456563223451234534556234534554532345623456456634564566"
    "56456756672123452345456623454545345656534555212345234545623454543455653455"
    "45323452345453454554565345344433453456563455545664545434456345564565564552"
    "34545664566565512343455344540",
    "65432345432123322343345454322342123423445323423443443234532345345523453455"
    "45345645563212342234345512343434234545423444321234223434512343432344542344"
    "34322341234342343443454234233432342345452344434553434343345234453454453443"
    "234345534554544212323442334310",
    "76543234543212432233334445432233212322334322312332354323443234334432342344"
    "34434534454321233223334421232323323434332333432123322333421232323233432233"
    "23432232123233232332343123122543233234343233333442323254334323343343342334"
    "3233344234434333212223312232210",
    "87654323654321543224333446543224321232233432221223265432354323433443233233"
    "23543443345432124322333432122212432333243232543212432233432122214323323223"
    "32543223212223221223232212213654324323334322243333232365433432334332433245"
    "43243343233434343213223213233210",
    "76543345543223321232234345433343223412334433423433454334532345234433453454"
    "45345645564322342123234422342334234534412333432234212323422342332343441233"
    "23432342234232343443454233233321232234341233323443333243234334342344343434"
    "334234434544533322312332334221120",
    "87654334654322432123223336543334322321223433322323365433443234323343342343"
    "34434534455432233212223332231223323423321222543223321222332231223232332122"
    "32543233223123232333343222222432123223232122232333222154323433233233433335"
    "4333233334334224322212222231321110",
    "98765444765433543223212227654445433332212544433324476544454334323254443343"
    "44544534456543334322212243332233433423332212654333432221243332234332333221"
    "43654334323224332334343322323543223212223221232322121265433432334332433236"
    "54443324443443354333221333324322210",
    "76543234543212432233334445432233212322334322312332354323443234334432342344"
    "34434534454321233223334421232323323434323343432123322333421232323233432334"
    "23432232123233232332343123122432333234342333334442323354344323343343342324"
    "323334423443433321222331223321011120",
    "87654323654321543224333446543224321232233432221223265432354323433443233233"
    "23543443345432124322333432122212432333232232543212432233432122214323323223"
    "32543223212223221223232212213543224323333222243333232265433432334332433235"
    "4324334323343334321322321322321021210",
    "87654345654323543234334446543344323432334433423433454323432123223332231233"
    "23323423345432344323334432342334212323232333543234432333432342332122323233"
    "33543343234234343443232233233543233234343233333332323243234212233232231215"
    "43432333343232243233233231223212212120",
    "87654345654323432123223336543344322321223543332324365434543234323343342343"
    "34434534455432343212223332231223323423321222543234321222332231223232332122"
    "32543233223123232334343322332432123223232122232333323154323323233233332325"
    "433323343433422432321223223132121012110",
    "65432345432345334564567674323452345645667234545664532345612345345523453455"
    "45345645562123452345456623454545234545434555101234123434512343432344542344"
    "34212342345452344543454345233323453456563455534554534443456234453454453443"
    "4563455456545442345456645344123434534440",
    "76543234543234433454456565432343234534556323434553443234521234234422342344"
    "34234534453212342234345512343434123434323444210123112323401232321233431233"
    "23321232234341233432343234122432342345452344423443423332345123342343342334"
    "34523443454343332343455342332123234233310",
    "87654323654323543344445556543234323433445432323442354323432123223332231233"
    "23323423344321233223334421232323212323232333321012211222310121212122322122"
    "12432123223332122322232123011543233234343233332332312243234212233232231225"
    "434323333432322432333442312232122231222210",
    "98765432765432654335444557654325432343344543232333265432343212322343222122"
    "22432332235432124322333432122212321222143232432101321122321011103212213212"
    "21543214322333212213221212102654324323334322243223221354323321223221322136"
    "5434323433232335432433432213432132321333210",
    "87654334654323432343345456543344323423445433423443454334532234123333342343"
    "34334534454322342123234422342334223423312333321123101212311231221232330122"
    "12432232123232232332343123122432343234342343412332322343345223233343232325"
    "43433433454343243232344232323223123233221120",
    "98765433765432543234334447654335432332334543332333365433443223212243332232"
    "33433423345432233212223332231223322312221222432112210111221120112121221011"
    "21543223212223221223232212112543234323233232321223221254334322124332322226"
    "543433243433321543232333222143222122221321110",
    "87654323654323543344445556543234323433445432323442354323432123223332231233"
    "23323423344321233223334421232323212323222333321012211222310121212122321223"
    "12432123223332122322232123011543233234343233323332312243234212233232231215"
    "4343233334323224323334423122321222312232101110",
    "98765434765433654345445557654345433443445543433443465432343234323343232343"
    "23323412235432344323334432342334212323232333432123321222321231221011212122"
    "22543234323333232332122223122654344334344343432332312254323323233233231206"
    "54343434344342154334344332324323323231232122110",
    "54321234432234233454456563212341234534556123434553421234501234234412342344"
    "34234534453233451234345523453445123434323444212345234545623454542344543455"
    "45212342345452344543453344343323452345453454523443445432345123342343342334"
    "345234434543434343434553423323454564534123434340",
    "65432123543223323343445554321232123423445212323442332123410123123321231233"
    "23123423344322342123234412342334012323212333321234223434512343431233432344"
    "34321232234341233432342233232322341234342343412332334321234012231232231223"
    "2341233234323234323234423122323434534232123232310",
    "76543212654322432333344455432123212322334321212331243212321012112221120122"
    "12212312235432233212223321231223101212121222432123322333421232322122323233"
    "23432123223332122323231222121432232123233232321221223232123101122121120114"
    "32321222232121243322233120114323334231232122212210",
    "76543223543212432232334445432233212312334322312332343223421123012232231232"
    "23223423344321233223123321232323112312222323432234212323422342332232331233"
    "23432232123232232331232123232433332234231233301221223332234112122232121224"
    "323223223432323321222331212243232342323322312232110",
    "87654322654321543223233346543224321221223432221222254322332112101132221121"
    "22322312235432124322212232121212211201132212543223321222332231223221222122"
    "32543223212223221222121212222543323223122122210112132243223211013221211125"
    "4323221323222224321322221112543232332224322212232110",
    "76543212654322432333344455432123212322334321212331243212321012112221120122"
    "12212312235432333212223321231223101212121222432123322333421232322122322233"
    "23432123223332122322231232121432232123232232312221223232123101122121120114"
    "32321222232121243232233120114323334231232122212210110",
    "43210123321123222343345452101231123423445012323442332123412345345512343455"
    "34234545453222342334445522343434234545434454212345234545623454543455653455"
    "45101231234341233432344234342212342345452344434553445332345234453454453444"
    "334345534554545432333442334434344453445234545451233430",
    "54321012432112322233334443210122112322334101212331243212321234234421232344"
    "23223434344321233223334421232323123434323343321234223434512343432344542344"
    "34210121123230122321233123231321232234341233323442334232234123342343342334"
    "3232344234434343212223312233432333423343234343421223210",
    "65432101543211432223333444321013211222233210111220154321232123223332121233"
    "12322323235432124322333432122212212323232232432123322333421232323233433233"
    "23321012112221011212122212120432123223332122232332223143223212233232231225"
    "43232333233232343213223211225432434322343233323321221210",
    "65432112432101321122223334321122101211223211201221243212332123123321231233"
    "23323423343210122112223310121212212323222232432123212323421232322233431233"
    "23321121012121121221232012121432222123232222212331223243223223232233232333"
    "212223312332333210111220112232122231223432323233221222110",
    "65432101543211432223333444321013211222233210111220154321232123223332121233"
    "12322323234321223223334421222322212323232333432123322333421232323233432334"
    "23321012112221011212122123120432123223332122222332323143212212232122221224"
    "3223233223323233212223312122432333423234323332332122121010",
    "54321234432234212342345453212342234523445123434543443234523456345523454565"
    "45345656563233451234345523453445345645523444323456234545634564554565663455"
    "45212342345342344543455344453212342345452344434553445332345345563455454554"
    "34534554565564543342344344534445345455434564556234454123330",
    "65432123543223321232234344321233223412334212323432354323432345234432343454"
    "34334545454322342123234432342334234534412333432345323434523453443454552344"
    "34321232234231233432344233342321232234341233323442334243234234452344343444"
    "334234434544534322312332334243342343443434534453233432122210",
    "76543212654322432123223335432124322321223321222321265432343234323343232343"
    "23433434345432233212223332231223323423321222543234432323432342334343443233"
    "33432123223122122323233322231432123223232122232333223154323323343233332335"
    "4333233434334234322212232231543332343325434433443233232121210",
    "76543223543212432232123235432233212322323322312332354323443234234332342344"
    "34434534454321233223123321232323323434322323543234323423432343433344542343"
    "34432232123232232332343123232432232123232232323431223254334323343343342334"
    "32333432344343432122232122324323333233354343434433233322122110",
    "54322345321234101231234344323452123412334223423433432234512345234423453454"
    "45345645562123450123234412342334234534412333323456123434523453443454552344"
    "34212342345232343443454343453101231234341233323442334221234234452344343443"
    "234234434544534323412332334243452343443445634453444442344412330",
    "65432234432123210121123234322342112301223322312322343223421234123332342343"
    "34234534453212341012123321231223123423301222432345212323422342332343441233"
    "23321232234121232332343232342210121123230122212331223132123223341233232333"
    "2231233234334232123012212231323412323324345233443333332333212210",
    "65433456432345212342345454323453234523445234534544532123422345345512343455"
    "34234545453223451234345523453445334545423444433456234545634564553455653455"
    "45323453456343454552344344454212342345452344434553445321234234452344343443"
    "23434553455454543452344343435456345454454453445443443344542344120",
    "76543345543234321232234345432343223412334323423433443212332234234421232344"
    "23323434344322342123234432342334223434312333543345323434533453442344542344"
    "34432343345232343441233233343321232234341233323442334232123223341233232334"
    "323234423443434323412332323243452343433433423344323324334332332110",
    "65434567432345323453456563212342234534556123434553421012311234234401232344"
    "23123434343212342234345512343434223434333444322345123434523453442344542344"
    "34323452345452344541233234344212342345452344423443434310123123341233232332"
    "1232344234434343234345534233434534545344334233443233244343344523120"};
const int maxn = 2e3 + 100;
const int N = 2e3;
int prime[N], tot;
bitset<maxn> p;
void work1() {
  for (int i = 2; i <= N; i++) {
    if (!p[i]) {
      tot++;
      prime[tot] = i;
    }
    for (int j = 1; j <= tot; j++) {
      if (prime[j] * i > N) break;
      p[i * prime[j]] = 1;
      if (i % prime[j] == 0) break;
    }
  }
}
int F[30];
int x, y, sum;
struct node {
  int a[8];
};
bool cmp(int aa, int bb) { return bb < aa; }
int find(int y) {
  node x;
  int cnt = 0;
  for (int i = 0; i < 7; i++) x.a[i] = 0;
  for (int i = 1; prime[i] * prime[i] <= y && i <= tot; i++)
    if (y % prime[i] == 0) {
      while (y % prime[i] == 0) {
        y /= prime[i];
        x.a[cnt]++;
      }
      cnt++;
      if (y == 1) break;
    }
  if (y != 1) {
    x.a[cnt] = 1;
    cnt++;
  }
  sort(x.a, x.a + 7, cmp);
  for (int i = F[x.a[0]];; i++) {
    bool flag = true;
    for (int j = 1; j < 7; j++) {
      if (Map[i][j] != x.a[j]) {
        flag = false;
        break;
      }
    }
    if (flag) return i;
  }
}
int main() {
  work1();
  int T = read();
  for (int i = 0; i < 289; i++) {
    if (!F[Map[i][0]]) F[Map[i][0]] = i;
  }
  while (T--) {
    x = read(), y = read();
    x = find(x);
    y = find(y);
    if (x > y) swap(x, y);
    sum = dis[y][x] == ':' ? 10 : dis[y][x] - '0';
    write(sum);
    putchar('\n');
  }
  return 0;
}