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;
template <typename T, typename U>
std::istream& operator>>(std::istream& i, pair<T, U>& p) {
  i >> p.first >> p.second;
  return i;
}
template <typename T>
std::istream& operator>>(std::istream& i, vector<T>& t) {
  for (auto& v : t) {
    i >> v;
  }
  return i;
}
template <typename T, typename U>
std::ostream& operator<<(std::ostream& o, const pair<T, U>& p) {
  o << p.first << ' ' << p.second;
  return o;
}
template <typename T>
std::ostream& operator<<(std::ostream& o, const vector<T>& t) {
  if (t.empty()) o << '\n';
  for (size_t i = 0; i < t.size(); ++i) {
    o << t[i] << " \n"[i == t.size() - 1];
  }
  return o;
}
template <typename T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <typename T>
using maxheap = priority_queue<T, vector<T>, less<T>>;
template <typename T>
bool in(T a, T b, T c) {
  return a <= b && b < c;
}
unsigned int logceil(int first) {
  return first ? 8 * sizeof(int) - __builtin_clz(first) : 0;
}
namespace std {
template <typename T, typename U>
struct hash<pair<T, U>> {
  hash<T> t;
  hash<U> u;
  size_t operator()(const pair<T, U>& p) const {
    return t(p.first) ^ (u(p.second) << 7);
  }
};
}  // namespace std
template <typename T, typename F>
T bsh(T l, T h, const F& f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      l = m + 1;
      r = m;
    } else {
      h = m - 1;
    }
  }
  return r;
}
template <typename F>
double bshd(double l, double h, const F& f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      l = m;
    } else {
      h = m;
    }
  }
  return (l + h) / 2;
}
template <typename T, typename F>
T bsl(T l, T h, const F& f) {
  T r = -1, m;
  while (l <= h) {
    m = (l + h) / 2;
    if (f(m)) {
      h = m - 1;
      r = m;
    } else {
      l = m + 1;
    }
  }
  return r;
}
template <typename F>
double bsld(double l, double h, const F& f, double p = 1e-9) {
  unsigned int r = 3 + (unsigned int)log2((h - l) / p);
  while (r--) {
    double m = (l + h) / 2;
    if (f(m)) {
      h = m;
    } else {
      l = m;
    }
  }
  return (l + h) / 2;
}
template <typename T>
T gcd(T a, T b) {
  if (a < b) swap(a, b);
  return b ? gcd(b, a % b) : a;
}
template <typename T>
class vector2 : public vector<vector<T>> {
 public:
  vector2() {}
  vector2(size_t a, size_t b, T t = T())
      : vector<vector<T>>(a, vector<T>(b, t)) {}
};
template <typename T>
class vector3 : public vector<vector2<T>> {
 public:
  vector3() {}
  vector3(size_t a, size_t b, size_t c, T t = T())
      : vector<vector2<T>>(a, vector2<T>(b, c, t)) {}
};
template <typename T>
class vector4 : public vector<vector3<T>> {
 public:
  vector4() {}
  vector4(size_t a, size_t b, size_t c, size_t d, T t = T())
      : vector<vector3<T>>(a, vector3<T>(b, c, d, t)) {}
};
template <typename T>
class vector5 : public vector<vector4<T>> {
 public:
  vector5() {}
  vector5(size_t a, size_t b, size_t c, size_t d, size_t e, T t = T())
      : vector<vector4<T>>(a, vector4<T>(b, c, d, e, t)) {}
};
class TaskD {
 public:
  vector<int> P;
  void fact(int a, vector<int>& f) {
    while (a != 1) {
      int b = P[a], c = 0;
      while (P[a] == b) {
        c++;
        a /= b;
      }
      f.push_back(c + 1);
    }
    sort(f.begin(), f.end());
    reverse(f.begin(), f.end());
    while (f.size() < Prm.size()) f.push_back(1);
  }
  vector<vector<int>> HH;
  vector<int> Used, CNT;
  map<vector<int>, int> J;
  vector<int> X;
  void genAll(int p, int m, int c, int d) {
    if (p == Prm.size()) {
      HH.push_back(X);
      CNT.push_back(d);
      int second = J.size();
      if (c <= 1e6) Used.push_back(second);
      J[X] = second;
    } else {
      X[p] = 1;
      genAll(p + 1, 1, c, d * X[p]);
      while (true) {
        X[p]++;
        c *= Prm[p];
        if (c > 55050240) return;
        if (X[p] > m) return;
        genAll(p + 1, X[p], c, d * X[p]);
      }
    }
  }
  vector<int> Prm;
  void solve(istream& cin, ostream& cout) {
    Prm = {2, 3, 5, 7, 11, 13, 17};
    P.assign(1e6 + 5, 0);
    for (int i = 2; i < 1e6 + 3; ++i) {
      if (P[i] == 0) {
        for (int j = i; j < 1e6 + 3; j += i) P[j] = i;
      }
    }
    map<vector<int>, int> IDX{
        {{1, 1, 1, 1, 1, 1, 1}, 0},    {{2, 1, 1, 1, 1, 1, 1}, 1},
        {{2, 2, 1, 1, 1, 1, 1}, 2},    {{2, 2, 2, 1, 1, 1, 1}, 3},
        {{2, 2, 2, 2, 1, 1, 1}, 4},    {{2, 2, 2, 2, 2, 1, 1}, 5},
        {{2, 2, 2, 2, 2, 2, 1}, 6},    {{2, 2, 2, 2, 2, 2, 2}, 7},
        {{3, 1, 1, 1, 1, 1, 1}, 8},    {{3, 2, 1, 1, 1, 1, 1}, 9},
        {{3, 2, 2, 1, 1, 1, 1}, 10},   {{3, 2, 2, 2, 1, 1, 1}, 11},
        {{3, 2, 2, 2, 2, 1, 1}, 12},   {{3, 2, 2, 2, 2, 2, 1}, 13},
        {{3, 3, 1, 1, 1, 1, 1}, 14},   {{3, 3, 2, 1, 1, 1, 1}, 15},
        {{3, 3, 2, 2, 1, 1, 1}, 16},   {{3, 3, 2, 2, 2, 1, 1}, 17},
        {{3, 3, 2, 2, 2, 2, 1}, 18},   {{3, 3, 3, 1, 1, 1, 1}, 19},
        {{3, 3, 3, 2, 1, 1, 1}, 20},   {{3, 3, 3, 2, 2, 1, 1}, 21},
        {{3, 3, 3, 2, 2, 2, 1}, 22},   {{3, 3, 3, 3, 1, 1, 1}, 23},
        {{3, 3, 3, 3, 2, 1, 1}, 24},   {{4, 1, 1, 1, 1, 1, 1}, 25},
        {{4, 2, 1, 1, 1, 1, 1}, 26},   {{4, 2, 2, 1, 1, 1, 1}, 27},
        {{4, 2, 2, 2, 1, 1, 1}, 28},   {{4, 2, 2, 2, 2, 1, 1}, 29},
        {{4, 2, 2, 2, 2, 2, 1}, 30},   {{4, 3, 1, 1, 1, 1, 1}, 31},
        {{4, 3, 2, 1, 1, 1, 1}, 32},   {{4, 3, 2, 2, 1, 1, 1}, 33},
        {{4, 3, 2, 2, 2, 1, 1}, 34},   {{4, 3, 2, 2, 2, 2, 1}, 35},
        {{4, 3, 3, 1, 1, 1, 1}, 36},   {{4, 3, 3, 2, 1, 1, 1}, 37},
        {{4, 3, 3, 2, 2, 1, 1}, 38},   {{4, 3, 3, 3, 1, 1, 1}, 39},
        {{4, 3, 3, 3, 2, 1, 1}, 40},   {{4, 4, 1, 1, 1, 1, 1}, 41},
        {{4, 4, 2, 1, 1, 1, 1}, 42},   {{4, 4, 2, 2, 1, 1, 1}, 43},
        {{4, 4, 2, 2, 2, 1, 1}, 44},   {{4, 4, 3, 1, 1, 1, 1}, 45},
        {{4, 4, 3, 2, 1, 1, 1}, 46},   {{4, 4, 3, 2, 2, 1, 1}, 47},
        {{4, 4, 3, 3, 1, 1, 1}, 48},   {{4, 4, 4, 1, 1, 1, 1}, 49},
        {{4, 4, 4, 2, 1, 1, 1}, 50},   {{5, 1, 1, 1, 1, 1, 1}, 51},
        {{5, 2, 1, 1, 1, 1, 1}, 52},   {{5, 2, 2, 1, 1, 1, 1}, 53},
        {{5, 2, 2, 2, 1, 1, 1}, 54},   {{5, 2, 2, 2, 2, 1, 1}, 55},
        {{5, 2, 2, 2, 2, 2, 1}, 56},   {{5, 3, 1, 1, 1, 1, 1}, 57},
        {{5, 3, 2, 1, 1, 1, 1}, 58},   {{5, 3, 2, 2, 1, 1, 1}, 59},
        {{5, 3, 2, 2, 2, 1, 1}, 60},   {{5, 3, 2, 2, 2, 2, 1}, 61},
        {{5, 3, 3, 1, 1, 1, 1}, 62},   {{5, 3, 3, 2, 1, 1, 1}, 63},
        {{5, 3, 3, 2, 2, 1, 1}, 64},   {{5, 3, 3, 3, 1, 1, 1}, 65},
        {{5, 4, 1, 1, 1, 1, 1}, 66},   {{5, 4, 2, 1, 1, 1, 1}, 67},
        {{5, 4, 2, 2, 1, 1, 1}, 68},   {{5, 4, 2, 2, 2, 1, 1}, 69},
        {{5, 4, 3, 1, 1, 1, 1}, 70},   {{5, 4, 3, 2, 1, 1, 1}, 71},
        {{5, 4, 3, 2, 2, 1, 1}, 72},   {{5, 4, 3, 3, 1, 1, 1}, 73},
        {{5, 4, 4, 1, 1, 1, 1}, 74},   {{5, 4, 4, 2, 1, 1, 1}, 75},
        {{5, 5, 1, 1, 1, 1, 1}, 76},   {{5, 5, 2, 1, 1, 1, 1}, 77},
        {{5, 5, 2, 2, 1, 1, 1}, 78},   {{5, 5, 2, 2, 2, 1, 1}, 79},
        {{5, 5, 3, 1, 1, 1, 1}, 80},   {{5, 5, 3, 2, 1, 1, 1}, 81},
        {{5, 5, 4, 1, 1, 1, 1}, 82},   {{5, 5, 5, 1, 1, 1, 1}, 83},
        {{6, 1, 1, 1, 1, 1, 1}, 84},   {{6, 2, 1, 1, 1, 1, 1}, 85},
        {{6, 2, 2, 1, 1, 1, 1}, 86},   {{6, 2, 2, 2, 1, 1, 1}, 87},
        {{6, 2, 2, 2, 2, 1, 1}, 88},   {{6, 2, 2, 2, 2, 2, 1}, 89},
        {{6, 3, 1, 1, 1, 1, 1}, 90},   {{6, 3, 2, 1, 1, 1, 1}, 91},
        {{6, 3, 2, 2, 1, 1, 1}, 92},   {{6, 3, 2, 2, 2, 1, 1}, 93},
        {{6, 3, 3, 1, 1, 1, 1}, 94},   {{6, 3, 3, 2, 1, 1, 1}, 95},
        {{6, 3, 3, 2, 2, 1, 1}, 96},   {{6, 3, 3, 3, 1, 1, 1}, 97},
        {{6, 4, 1, 1, 1, 1, 1}, 98},   {{6, 4, 2, 1, 1, 1, 1}, 99},
        {{6, 4, 2, 2, 1, 1, 1}, 100},  {{6, 4, 2, 2, 2, 1, 1}, 101},
        {{6, 4, 3, 1, 1, 1, 1}, 102},  {{6, 4, 3, 2, 1, 1, 1}, 103},
        {{6, 4, 4, 1, 1, 1, 1}, 104},  {{6, 4, 4, 2, 1, 1, 1}, 105},
        {{6, 5, 1, 1, 1, 1, 1}, 106},  {{6, 5, 2, 1, 1, 1, 1}, 107},
        {{6, 5, 2, 2, 1, 1, 1}, 108},  {{6, 5, 2, 2, 2, 1, 1}, 109},
        {{6, 5, 3, 1, 1, 1, 1}, 110},  {{6, 5, 3, 2, 1, 1, 1}, 111},
        {{6, 5, 4, 1, 1, 1, 1}, 112},  {{6, 6, 1, 1, 1, 1, 1}, 113},
        {{6, 6, 2, 1, 1, 1, 1}, 114},  {{6, 6, 2, 2, 1, 1, 1}, 115},
        {{6, 6, 3, 1, 1, 1, 1}, 116},  {{6, 6, 4, 1, 1, 1, 1}, 117},
        {{7, 1, 1, 1, 1, 1, 1}, 118},  {{7, 2, 1, 1, 1, 1, 1}, 119},
        {{7, 2, 2, 1, 1, 1, 1}, 120},  {{7, 2, 2, 2, 1, 1, 1}, 121},
        {{7, 2, 2, 2, 2, 1, 1}, 122},  {{7, 2, 2, 2, 2, 2, 1}, 123},
        {{7, 3, 1, 1, 1, 1, 1}, 124},  {{7, 3, 2, 1, 1, 1, 1}, 125},
        {{7, 3, 2, 2, 1, 1, 1}, 126},  {{7, 3, 2, 2, 2, 1, 1}, 127},
        {{7, 3, 3, 1, 1, 1, 1}, 128},  {{7, 3, 3, 2, 1, 1, 1}, 129},
        {{7, 3, 3, 3, 1, 1, 1}, 130},  {{7, 4, 1, 1, 1, 1, 1}, 131},
        {{7, 4, 2, 1, 1, 1, 1}, 132},  {{7, 4, 2, 2, 1, 1, 1}, 133},
        {{7, 4, 2, 2, 2, 1, 1}, 134},  {{7, 4, 3, 1, 1, 1, 1}, 135},
        {{7, 4, 3, 2, 1, 1, 1}, 136},  {{7, 4, 4, 1, 1, 1, 1}, 137},
        {{7, 5, 1, 1, 1, 1, 1}, 138},  {{7, 5, 2, 1, 1, 1, 1}, 139},
        {{7, 5, 2, 2, 1, 1, 1}, 140},  {{7, 5, 3, 1, 1, 1, 1}, 141},
        {{7, 5, 3, 2, 1, 1, 1}, 142},  {{7, 5, 4, 1, 1, 1, 1}, 143},
        {{7, 6, 1, 1, 1, 1, 1}, 144},  {{7, 6, 2, 1, 1, 1, 1}, 145},
        {{7, 6, 2, 2, 1, 1, 1}, 146},  {{7, 6, 3, 1, 1, 1, 1}, 147},
        {{7, 7, 1, 1, 1, 1, 1}, 148},  {{7, 7, 2, 1, 1, 1, 1}, 149},
        {{8, 1, 1, 1, 1, 1, 1}, 150},  {{8, 2, 1, 1, 1, 1, 1}, 151},
        {{8, 2, 2, 1, 1, 1, 1}, 152},  {{8, 2, 2, 2, 1, 1, 1}, 153},
        {{8, 2, 2, 2, 2, 1, 1}, 154},  {{8, 3, 1, 1, 1, 1, 1}, 155},
        {{8, 3, 2, 1, 1, 1, 1}, 156},  {{8, 3, 2, 2, 1, 1, 1}, 157},
        {{8, 3, 2, 2, 2, 1, 1}, 158},  {{8, 3, 3, 1, 1, 1, 1}, 159},
        {{8, 3, 3, 2, 1, 1, 1}, 160},  {{8, 4, 1, 1, 1, 1, 1}, 161},
        {{8, 4, 2, 1, 1, 1, 1}, 162},  {{8, 4, 2, 2, 1, 1, 1}, 163},
        {{8, 4, 3, 1, 1, 1, 1}, 164},  {{8, 4, 3, 2, 1, 1, 1}, 165},
        {{8, 4, 4, 1, 1, 1, 1}, 166},  {{8, 5, 1, 1, 1, 1, 1}, 167},
        {{8, 5, 2, 1, 1, 1, 1}, 168},  {{8, 5, 2, 2, 1, 1, 1}, 169},
        {{8, 5, 3, 1, 1, 1, 1}, 170},  {{8, 6, 1, 1, 1, 1, 1}, 171},
        {{8, 6, 2, 1, 1, 1, 1}, 172},  {{8, 6, 3, 1, 1, 1, 1}, 173},
        {{8, 7, 1, 1, 1, 1, 1}, 174},  {{8, 7, 2, 1, 1, 1, 1}, 175},
        {{8, 8, 1, 1, 1, 1, 1}, 176},  {{9, 1, 1, 1, 1, 1, 1}, 177},
        {{9, 2, 1, 1, 1, 1, 1}, 178},  {{9, 2, 2, 1, 1, 1, 1}, 179},
        {{9, 2, 2, 2, 1, 1, 1}, 180},  {{9, 2, 2, 2, 2, 1, 1}, 181},
        {{9, 3, 1, 1, 1, 1, 1}, 182},  {{9, 3, 2, 1, 1, 1, 1}, 183},
        {{9, 3, 2, 2, 1, 1, 1}, 184},  {{9, 3, 2, 2, 2, 1, 1}, 185},
        {{9, 3, 3, 1, 1, 1, 1}, 186},  {{9, 3, 3, 2, 1, 1, 1}, 187},
        {{9, 4, 1, 1, 1, 1, 1}, 188},  {{9, 4, 2, 1, 1, 1, 1}, 189},
        {{9, 4, 2, 2, 1, 1, 1}, 190},  {{9, 4, 3, 1, 1, 1, 1}, 191},
        {{9, 4, 4, 1, 1, 1, 1}, 192},  {{9, 5, 1, 1, 1, 1, 1}, 193},
        {{9, 5, 2, 1, 1, 1, 1}, 194},  {{9, 5, 2, 2, 1, 1, 1}, 195},
        {{9, 5, 3, 1, 1, 1, 1}, 196},  {{9, 6, 1, 1, 1, 1, 1}, 197},
        {{9, 6, 2, 1, 1, 1, 1}, 198},  {{9, 7, 1, 1, 1, 1, 1}, 199},
        {{9, 7, 2, 1, 1, 1, 1}, 200},  {{9, 8, 1, 1, 1, 1, 1}, 201},
        {{10, 1, 1, 1, 1, 1, 1}, 202}, {{10, 2, 1, 1, 1, 1, 1}, 203},
        {{10, 2, 2, 1, 1, 1, 1}, 204}, {{10, 2, 2, 2, 1, 1, 1}, 205},
        {{10, 2, 2, 2, 2, 1, 1}, 206}, {{10, 3, 1, 1, 1, 1, 1}, 207},
        {{10, 3, 2, 1, 1, 1, 1}, 208}, {{10, 3, 2, 2, 1, 1, 1}, 209},
        {{10, 3, 3, 1, 1, 1, 1}, 210}, {{10, 3, 3, 2, 1, 1, 1}, 211},
        {{10, 4, 1, 1, 1, 1, 1}, 212}, {{10, 4, 2, 1, 1, 1, 1}, 213},
        {{10, 4, 2, 2, 1, 1, 1}, 214}, {{10, 4, 3, 1, 1, 1, 1}, 215},
        {{10, 5, 1, 1, 1, 1, 1}, 216}, {{10, 5, 2, 1, 1, 1, 1}, 217},
        {{10, 6, 1, 1, 1, 1, 1}, 218}, {{10, 6, 2, 1, 1, 1, 1}, 219},
        {{10, 7, 1, 1, 1, 1, 1}, 220}, {{11, 1, 1, 1, 1, 1, 1}, 221},
        {{11, 2, 1, 1, 1, 1, 1}, 222}, {{11, 2, 2, 1, 1, 1, 1}, 223},
        {{11, 2, 2, 2, 1, 1, 1}, 224}, {{11, 3, 1, 1, 1, 1, 1}, 225},
        {{11, 3, 2, 1, 1, 1, 1}, 226}, {{11, 3, 2, 2, 1, 1, 1}, 227},
        {{11, 3, 3, 1, 1, 1, 1}, 228}, {{11, 4, 1, 1, 1, 1, 1}, 229},
        {{11, 4, 2, 1, 1, 1, 1}, 230}, {{11, 4, 2, 2, 1, 1, 1}, 231},
        {{11, 4, 3, 1, 1, 1, 1}, 232}, {{11, 5, 1, 1, 1, 1, 1}, 233},
        {{11, 5, 2, 1, 1, 1, 1}, 234}, {{11, 6, 1, 1, 1, 1, 1}, 235},
        {{11, 7, 1, 1, 1, 1, 1}, 236}, {{12, 1, 1, 1, 1, 1, 1}, 237},
        {{12, 2, 1, 1, 1, 1, 1}, 238}, {{12, 2, 2, 1, 1, 1, 1}, 239},
        {{12, 2, 2, 2, 1, 1, 1}, 240}, {{12, 3, 1, 1, 1, 1, 1}, 241},
        {{12, 3, 2, 1, 1, 1, 1}, 242}, {{12, 3, 2, 2, 1, 1, 1}, 243},
        {{12, 3, 3, 1, 1, 1, 1}, 244}, {{12, 4, 1, 1, 1, 1, 1}, 245},
        {{12, 4, 2, 1, 1, 1, 1}, 246}, {{12, 5, 1, 1, 1, 1, 1}, 247},
        {{12, 5, 2, 1, 1, 1, 1}, 248}, {{12, 6, 1, 1, 1, 1, 1}, 249},
        {{13, 1, 1, 1, 1, 1, 1}, 250}, {{13, 2, 1, 1, 1, 1, 1}, 251},
        {{13, 2, 2, 1, 1, 1, 1}, 252}, {{13, 2, 2, 2, 1, 1, 1}, 253},
        {{13, 3, 1, 1, 1, 1, 1}, 254}, {{13, 3, 2, 1, 1, 1, 1}, 255},
        {{13, 3, 3, 1, 1, 1, 1}, 256}, {{13, 4, 1, 1, 1, 1, 1}, 257},
        {{13, 4, 2, 1, 1, 1, 1}, 258}, {{13, 5, 1, 1, 1, 1, 1}, 259},
        {{13, 6, 1, 1, 1, 1, 1}, 260}, {{14, 1, 1, 1, 1, 1, 1}, 261},
        {{14, 2, 1, 1, 1, 1, 1}, 262}, {{14, 2, 2, 1, 1, 1, 1}, 263},
        {{14, 2, 2, 2, 1, 1, 1}, 264}, {{14, 3, 1, 1, 1, 1, 1}, 265},
        {{14, 3, 2, 1, 1, 1, 1}, 266}, {{14, 4, 1, 1, 1, 1, 1}, 267},
        {{14, 5, 1, 1, 1, 1, 1}, 268}, {{15, 1, 1, 1, 1, 1, 1}, 269},
        {{15, 2, 1, 1, 1, 1, 1}, 270}, {{15, 2, 2, 1, 1, 1, 1}, 271},
        {{15, 3, 1, 1, 1, 1, 1}, 272}, {{15, 3, 2, 1, 1, 1, 1}, 273},
        {{15, 4, 1, 1, 1, 1, 1}, 274}, {{16, 1, 1, 1, 1, 1, 1}, 275},
        {{16, 2, 1, 1, 1, 1, 1}, 276}, {{16, 2, 2, 1, 1, 1, 1}, 277},
        {{16, 3, 1, 1, 1, 1, 1}, 278}, {{16, 4, 1, 1, 1, 1, 1}, 279},
        {{17, 1, 1, 1, 1, 1, 1}, 280}, {{17, 2, 1, 1, 1, 1, 1}, 281},
        {{17, 2, 2, 1, 1, 1, 1}, 282}, {{17, 3, 1, 1, 1, 1, 1}, 283},
        {{18, 1, 1, 1, 1, 1, 1}, 284}, {{18, 2, 1, 1, 1, 1, 1}, 285},
        {{19, 1, 1, 1, 1, 1, 1}, 286}, {{19, 2, 1, 1, 1, 1, 1}, 287},
        {{20, 1, 1, 1, 1, 1, 1}, 288}};
    vector<string> DIST{
        "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",
        "876543217654326543254334465432154321432334321321221543210432113223321"
        "0",
        "7654322354321243212322333543223321232122332231232234321122101211222112"
        "0",
        "8765432265432154321432233654322432123212243222121225432113210121123211"
        "10",
        "9876543276543265432543243765432543214323254323212326543214321032124321"
        "210",
        "9876543376543254321432132765433543223212154333221336543224321121014322"
        "2110",
        "7654321265432154322433344543212432123223332122122124321013211222232101"
        "11220",
        "8765432176543265432543344654321543214323343213212215432104321132233210"
        "211210",
        "6543234554323443234334545432345323452344523453454453212342123423441234"
        "2344340",
        "7654323465432354323433444543234432343233432342343344321233212322332123"
        "12332310",
        "8765432376543265432543344654323543234323343233232235432124321232233212"
        "212212210",
        "9876543287654376543654354765432654325434354324323326543215432143234321"
        "3212213210",
        "8765433465432354323432333654334432343232343342343345432233212321223223"
        "12322321120",
        "9876543376543265432543243765433543234323254333232336543224321232124322"
        "212122321110",
        "8765432376543265432543344654323543234323343233232235432124321232233212"
        "2122122101110",
        "9876543487654376543654354765434654345434354344343346543235432343234323"
        "32322332122110",
        "3212345610123412345345656212345123453455623453455451234562345645663456"
        "456656456756670",
        "4321234521012311234234545211234012342344512342344342123451234534552345"
        "3455453456455610",
        "5432123432101221123223434321123101231233421231233233212342123423441234"
        "23443423453445210",
        "6543212343210132112222333432112210121122321120122124321233212322332123"
        "123323323423343210",
        "7654321254321043211322233543211321012112232111011215432124321232233212"
        "2122124323322343210",
        "8765432165432154321432233654321432103212243212101216543215432143234321"
        "32122154324334543210",
        "5432234532112310123123434322234112341233422342343343223451234523442345"
        "345445345645562112340",
        "6543223443211221012112323432223211230122332231232234322342123412332234"
        "2343342345344532112310",
        "7654322354321132101211222543222321121011232221121225432233212321223223"
        "12322332342334432112210",
        "8765432265432143210321122654322432112101143222110326543224321232124322"
        "212122432332235432113210",
        "7654333454322232112101212543333322231121243332232335433343223412323334"
        "2343343345344543222321120",
        "8765433365432243211210111654333432222110143332221336543334322321214333"
        "22323343342334543222321110",
        "9876543376543254321321021765433543223211054333221437654335432232125433"
        "322133543332336543224321210",
        "9876544476543354322321110765444543333221154443332447654445433332215444"
        "3332445444334465433343222110",
        "5432123432101221123223434321123101231233421231233233212342123423441234"
        "23443423453445210123112323440",
        "6543212343210132112222333432112210121122321120122124321233212322332123"
        "123323323423343210122112223310",
        "7654321254321043211322233543211321012112232111011215432124321232233212"
        "2122124323322343210132112223210",
        "8765432165432154321432233654321432103212243212101216543215432143234321"
        "32122154324334543210432132233210",
        "7654322354321132101211222543222321121011232221121225432233212321223223"
        "123223323423344321122101112221120",
        "8765432265432143210321122654322432112101143222110326543224321232124322"
        "2121224323322354321132102112321110",
        "7654321254321043211322233543211321012112232111011215432124321232233212"
        "21221243233223432101321122232101110",
        "8765432165432154321432233654321432103212243212101216543215432143234321"
        "321221543243345432104321322332102110",
        "6543234543212332123223434432234212341233432342343343212341012312332123"
        "1233231234233432123421232344123423340",
        "7654323454321243212322333543223321232122332231232234321232101211222112"
        "01221221231223432123321222332123122310",
        "8765432365432154321432233654322432123212243222121325432123210121123211"
        "101121321221125432124321322332122112210",
        "9876543276543265432543243765432543214323254323212326543214321032124321"
        "2101214321322365432154324323432132213210",
        "8765433465432243212321222654333432232121243332232335432233211210113222"
        "11212232231223543223321221223223122321120",
        "9876543376543254321432132765433543223212154333221436543224321121014322"
        "211032432221226543224321321243222122321110",
        "8765432365432154321432233654322432123212243222121325432123210121123211"
        "1011213212211254321243213223321221122101110",
        "6543234543212321012112323432234211230122332231232234323452123412333234"
        "23433423453445321234101212332123122312342330",
        "7654323454321232101211222543223321121011243222121325432343212321223223"
        "123223323423344321232101112221120112212312210",
        "8765432365432143210321122654322432112101143222110326543234321232124322"
        "2121324323322354321232102112321110213212211210",
        "8765433465432243211210111654333432222110154333221436543344322321214333"
        "22323343342334543223321110113222112232231222110",
        "8765432365432143210321122654322432112101143222110326543234321232124322"
        "212132432332235432123210211232111021321221121010",
        "4321234521234523456456767212345234564566723454566452234563456756773456"
        "5677564567676712345634565677345656564567676456660",
        "5432123432123422345345656321234123453455612343455343223452345645662345"
        "45664534565656212345234545662345454534565653455510",
        "6543212343212332234334545432123212342344521232344234322343234534552234"
        "345534334545453212342234345512343434234545423444210",
        "7654321254321243223333444543212321232233432121233125432234323433443223"
        "2344234334343443212332233344212323233234343323333210",
        "8765432165432154322433344654321432123223343212122216543225432343344322"
        "32332254334334543212432233343212221243233324323243210",
        "9876543276543265432543344765432543214323354323212327654326543254345432"
        "432332654354456543215432433443213221543243354343543210",
        "6543223443212321234234545432234212342344522342344344323452234534552345"
        "3455453456455632123412343455123434342345454234442112340",
        "7654322354321232123223434543223321231233432231233235432343223423443234"
        "23443433453445432123212323442123232322343431233332112310",
        "8765432265432143212322333654322432122122343222122226543234322332334323"
        "223323433433345432123212223332121212322323221222432112210",
        "9876543276543254321432233765432543213212254323211327654325432243235432"
        "3222325433433465432143213223432121214322322321215432113210",
        "8765433365432243212212323654333432232122343332232336543344323422334334"
        "23433443453445543223321212333223122332342332122243222321120",
        "9876543376543254321321222765433543223211254333221337654335432332225433"
        "323233543433346543224321212243222122432322232111543222321110",
        ":987654487654365432432121876544654334322165444332448765446543343226544"
        "4332446544434476543354323211543332335433323432226543334322210",
        "6543212343212332234334545432123212342344521232344234322343234534552234"
        "34553433454545321234223434551234343423454542344421012311232340",
        "7654321254321243223333444543212321232233432121233125432234323433443223"
        "234423433434344321233223334421232323323434322333321012211222310",
        "8765432165432154322433344654321432123223343212122216543225432343344322"
        "3233225433433454321243223334321222124323332322324321013211223210",
        "9876543276543265432543344765432543214323354323212327654326543254345432"
        "43233265435445654321543243344321322154324334323254321043213233210",
        "8765432265432143212322333654322432122122343222122226543234322332334323"
        "223323433433345432123212223332121212322323221222432112210111221120",
        "9876543276543254321432233765432543213212254323211327654325432243235432"
        "3222325433433465432143213223432121214322322321215432113210212321110",
        "8765432165432154322433344654321432123223343212122216543225432343344322"
        "32332254334334543212432233343212221243233323223243210132112232101110",
        "7654323454322343234334545543234322342344532342344344321232123423442123"
        "234423223434344322343234345522343434123434323444321234212323412342330",
        "8765432365432254323433444654323432233233443232233235432123212322333212"
        "123312322323235432234323334432232323212323232333432123321222321231221"
        "0",
        "9876543276543265432543344765432543224323354323222326543214321232234321"
        "2122214322322365432254324334432232223212221432325432124321323321221121"
        "0",
        "9876543376543254322432333765433543233222354333232336543224321221224322"
        "2122224323222365432343223233432322233212121322225432233212212322312221"
        "10",
        ":987654387654365432543243876543654324323265434322437654325432132125432"
        "3211325432323376543254324323543232324321212432326543224321322432221232"
        "110",
        "9876543276543265432543344765432543224323354323222326543214321232234321"
        "2122214322322365432254324334432232223212221432325432124321323321221121"
        "0110",
        "7654323454321232123223434543223321231233432231233235432343223423443234"
        "2344343345344543212321232344212323232234343123333212341012123212312212"
        "32330",
        "8765432365432143212322333654322432122122343222122326543234322332334323"
        "2233234334333454321232122233321212123223232212224321232101112211201121"
        "212210",
        "9876543276543254321432233765432543213212254323211327654325432243235432"
        "3222325433433465432143213223432121214322322321215432123210212321110232"
        "1211210",
        "9876543376543254321321222765433543223211254333221437654335432332225433"
        "3232335434333465432243212122432221224323222321115432233211101322211232"
        "21222110",
        "8765432365432343234334545654323432342344543232344236543344334534554334"
        "3455344445454554323432343455323434343345454234444321232123234212323222"
        "334312330",
        "9876543276543254323433444765432543233233454323233327654335433443445433"
        "3344335444444565432343233344432323234334343323335432123212223321212132"
        "2232212210",
        "3210123421123412345345656101234123453455612343455342123452345645662345"
        "4566453456565622234523454566234545453456565345551234563456567345656545"
        "66764566560",
        "4321012332112321234234545210123112342344501232344233212342234534551234"
        "3455342345454532123412343455123434342345454234442123452345456234545434"
        "556534554510",
        "5432101243211232123223434321012211231233410121233124321233223423442123"
        "2344233234343443212321232344212323232234343123333212342234345123434323"
        "4454234434210",
        "6543210154321143212322333432101321122122321011122015432124322332333212"
        "2233124323332354321232122233321212123223232212224321233223234212323232"
        "33433233233210",
        "7654321065432154321432233543210432113212232102111106543215432243234321"
        "3222215432433465432143213223432121214322322321215432124322323321222143"
        "233243223243210",
        "5432112332101221123123434321123101231233411231233233212342123423441234"
        "2344342345344521012311232344012323231234343223333212341234345123434323"
        "4454234434211230",
        "6543211243210132112212323432112210121122321120122124321233212322332123"
        "1233233234233432101221121233101212122123232212224321232123234212323222"
        "33431233233211210",
        "7654321154321043211321222543211321012111232111011115432124321232223212"
        "2122124323322343210132112122210111013212221321115432123212223321212132"
        "223221223243211210",
        "8765432165432154321432132654321432103212143212101216543215432143234321"
        "3212215432433454321043213212321021104321322432226543214321322432121243"
        "2322321243543213210",
        "7654322254321132101211212543222321121011232221121225432233212321223223"
        "1232233234233443211221011122211201122123122101115432233212123322312232"
        "32332122324321221120",
        "8765432265432143210321121654322432112101143222110226543224321232124322"
        "2121224323322354321132102111321110113212211210106543224321212432221243"
        "222232114354321321110",
        "5432101243211232123223434321012211231233410121233124321233223423442123"
        "2344233234343432122321232344122323232334343123333212342234345123434323"
        "4454234434210121123230",
        "6543210154321143212322333432101321122122321011122015432124322332333212"
        "2233124323332343211232122233211212123223232212224321233223234212323232"
        "33432233233210121121210",
        "7654321065432154321432233543210432113212232102111106543215432243234321"
        "3222215432433454321143213223321121114322322321215432124322323321222143"
        "233232223243210321121210",
        "7654321154321043211321222543211321012111232111011115432124321232223212"
        "2122124323322343210132112122210111013212221212125432123212223321212132"
        "2232212232432112101112110",
        "8765432165432154321432132654321432103212143212101216543215432143234321"
        "3212215432433454321043213212321021104321322321216543214321322432121243"
        "23223212435432132102132110",
        "7654321065432154321432233543210432113212232102111106543215432243234321"
        "3222215432433454321243213223321221124323322321215432124322323321222143"
        "233232223243210321121210110",
        "6543212354321243223323434432123321232233421231233233210122112312331012"
        "1233122123232343212332232344212323232223232233334322343234345223434312"
        "3343234434321232123231232330",
        "7654321265432154322432333543212432123222332122122124321013211221222101"
        "1122013212221254321243223233321222123212121322225432234323334322323221"
        "22323233334321232122221212210",
        "8765432176543265432543243654321543214323243213212215432104321132123210"
        "2111104321322365432154324323432132214321212432326543225432433432232232"
        "122143234354321432132321211210",
        "8765432265432154321432232654322432123212243222121225432113210121113211"
        "1011113212211254321243213222321221122101110321216543234322323432322232"
        "1121322243543223212213221222110",
        "6543212343210132112212323432112210121122321120122124321233212322332123"
        "1233233234233432101221121233101212122123232222224321232123234212323222"
        "33431233233212310121221212212320",
        "7654321254321043211321222543211321012111232111011215432124321232223212"
        "2122124323322343210132112122210111013212221321115432123212223321212132"
        "223221223243212210111211011212110",
        "8765432265432143210321121654322432112101143222110326543224321232124322"
        "2121224323322354321132102111321110113212211210106543224321212432221243"
        "2222321143543213211103211113221210",
        "7654321254321243223323434543212321232233432121233125432234323433443223"
        "2344234334343443212332232344212323233234343323333210122112123101212121"
        "22322222124321221232321223222331230",
        "8765432165432154322432333654321432123222343212122216543225432343334322"
        "3233225433433454321243223233321222124323332432224321013211212210111032"
        "122132112154321321222321121322221210",
        "6543210154321143212322323432101321122122321011122015432124322332333212"
        "2233124323332354322232122233322212223233233212224321233223234212323232"
        "3343323323321012112121011212122222120",
        "4321234521234501234234545212345123452344523453454452123452345634552345"
        "4565453456565632345612343455234534453456455234442345672345456345645545"
        "65663455451234534563434545534554545640",
        "5432123432123410123123434321234212341233412342343343212341234523441234"
        "3454342345454521234501232344123423342345344123333234561234345234534434"
        "545523443421234234523234344234434345310",
        "6543212343212321012112323432123211230122321231232234321232123412332123"
        "2343232234343432123410121233212312231234233012224323452123234223423323"
        "4344123323321232234121232331233232342210",
        "7654321254321232101211222543212321121011232122121125432123212321223212"
        "1232123223232343212321011122211201122123122101115432343212123322312232"
        "32332122324321221230121212221223212313210",
        "8765432165432143210321122654321432112101143212110216543214321232124321"
        "2121214322322354321232102112321110213212211210106543234321212432221243"
        "222232114354321321210321211321121032243210",
        "6543223443212321123012323432234212341232322342343344322342123423432234"
        "2344342345344532123411231233123423341234343123234323452234234234534423"
        "4454234334322341234232343442343233343211230",
        "7654322354321232112101212543223321231121232231232235432233212312323223"
        "1233233234233443212321120122212312232123232112125432343223123323423332"
        "33432232334322321231222323322321222323211210",
        "8765432265432143211210111654322432122110143222121226543224321221214322"
        "2122224323222354321232111011321211123212121211016543234322212432322243"
        "223232214354322321211322122322121132243211210",
        "9876543276543254321321021765432543213211054323211327654325432132125432"
        "3211325432323365432143212101432121214321212321117654325432321543232354"
        "3323432254654324321214322124322321433543213210",
        "8765433365432243212211201654333432232121243332232336543334322321224333"
        "2232334334233454322332121121322312233223122212126543344323222433423343"
        "32333232435432332231232323332322223324321221120",
        "9876543376543254321321110765433543223211154333221337654335432232115433"
        "3221335433323365432243212110432221224322212321117654335432321543332354"
        "332343225465432432221432222432232143354321321110",
        "6543212343212321012112323432123211230122321231232234321232123412332123"
        "2343232234343432123410121233212312231234233012224323452123234223423323"
        "4344123323321232234121232331233232342210121123230",
        "7654321254321232101211222543212321121011232122121125432123212321223212"
        "1232123223232343212321011122211201122123122101115432343212123322312232"
        "32332122324321221230121212221222212313210121121210",
        "8765432165432143210321122654321432112101143212110216543214321232124321"
        "2121214322322354321232102112321110213212211210106543234321212432221243"
        "222232114354321321210321211321121032243210321121210",
        "8765432265432143211210111654322432122110143222121226543224321221214322"
        "2122224323222354321232111011321211123212121211016543234322212432322243"
        "2232322143543223212113221223221211322432112101112110",
        "8765432165432143210321122654321432112101143212110216543214321232124321"
        "2121214322322354321232102112321110213212211210106543234321212432221243"
        "22223211435432132121032121132112103224321032112121010",
        "7654323454322332123212323543234322341232332342343344321232123401222123"
        "1232232123232343223421231233323423342234122123235433453234234334534423"
        "423323433443234323423234344123323334332123212323123230",
        "8765432365432243212321222654323432232121243233232235432123212310113212"
        "2121123212121254322332122122322312232123011212126543344323223433423332"
        "3122323243543233223123232332122322332432123212122121210",
        "9876543276543254321432132765432543223212154323221326543214321221014321"
        "2110214321212265432243213212432221323212102321217654335432322543332343"
        "22124322546543243222143232232123214335432143212132121210",
        "9876543376543254322321221765433543233221254333232336543224321221104322"
        "2121224322212265432343222121432322233212111322127654345433322543433343"
        "222243325465433432322433233322132243354322321221322122110",
        "7654323454321232123101212543223321232121232231232235432343212312323223"
        "1233233234233443212321230122212312232123232223125432343234123323423332"
        "3343234234432342123233232332342123233321231012122121212320",
        "8765432365432143212210111654322432122110143222121326543234321221214322"
        "2122224323222354321232121011321221123212121212016543234323212432322243"
        "22323231435432332122232212232312123234321221011121101212110",
        "8765432365432343212212323654323432232122343232232236543234323422334323"
        "2343234334343454323432121233322312233234233212224321232123012212312221"
        "223232312354323323412323233323323212243212212323212222233120",
        "9876543276543254321321222765432543223211254323221327654325432332225432"
        "3232325433333465432343212122432221224323222321115432123212101321221132"
        "1121212032654324323214322224322321213543213212223211132222110",
        "7654321254321232101211212543212321121011232122121125432123212321223212"
        "1232123223232343212321011122211201122123122101115432343212123322312232"
        "32332122324321221230121212221223212313210121121210111212222120",
        "5432345632234512345345656212345234563455623454565451012341234534551234"
        "3455342345454521234523454566234545452345454345553234563456567345656534"
        "556545665623456345645345565234434545512345345656345553455455640",
        "6543234543223421234234545321234223452344512343454342101231123423440123"
        "2344231234343432123412343455123434341234343234444323452345456234545423"
        "4454345545323452345342344541233234344212342345452344423443445310",
        "7654323454322332123223434432123322341233421232343233210122112322331012"
        "1233122123232343212321232344212323232123232123335432343234345223434312"
        "33432344344323422342312334301221232333212322343412333123323342210",
        "8765432365432243212322333543212432232122332122232124321013211222232101"
        "1122013212221254321232122233321212123212221212226543234323234322323221"
        "223232334354323322312212232101121232243212322323212222122322313210",
        "9876543276543254321432233654321543223212243213221215432104321132233210"
        "2112104321322365432143213223432121214321322321217654325432323432232232"
        "1221432254654324322213212212101321433543214322323212132124332243210",
        "7654334554323432234123434432234212342343422342344343211231012312331123"
        "1233231234233443223421232344123423340123232123335433453234345234534412"
        "33432344344334523453423434412322333443223412343423434223323343211230",
        "8765433465432343223212323543223321232232332231233234321122101211222112"
        "0122122123122354322332121233212312231012121212226543344323234323423321"
        "223232334354334323423223233112122233343223212323223232122122323211210",
        "9876543376543254322321222654322432123221243222122225432113210121123211"
        "1011113212211265432243212122321221122101110321117654335432323432322232"
        "112143225465433432322322122211032143354322321222322123211213224321121"
        "0",
        "9876544476543354323322312654333432232122343332232335432223211210113222"
        "1121223223122365433343222122322312232112011322127654445433323433423332"
        "2122433254654344334233232332121322433543233223122122210112132243222211"
        "0",
        ":987654487654365432432221765433543223212254333221336543224321121014322"
        "2110224322212276543354323211432221223211101432218765446543432543332343"
        "2212543365765435433324322223211432544654324322213212121013243354322321"
        "10",
        "7654323454322332123223434432123322341233421232343233210122112322331012"
        "1233122123232343212321232344212323231223332123335432343234345223434312"
        "3343234434432342234231233430122123233321232234341233312332334221012112"
        "230",
        "8765432365432243212322333543212432232122332122232124321013211222232101"
        "1122013212221254321232122233321212122112221212226543234323234322323221"
        "2232323343543233223122122321011212322432123223232122221222223132101211"
        "2210",
        "9876543276543254321432233654321543223212243213221215432104321132233210"
        "2112104321322365432143213223432121213211221321217654325432323432232232"
        "1221432254654324322213212212101321433543214322323212132123232243210321"
        "22210",
        "9876543376543254322321222654322432123221243222122225432113210121123211"
        "1011113212211265432243212122321221122101110321117654335432323432322232"
        "1121432254654334323223221222110321433543223212223221221212132243211210"
        "112110",
        "8765434565433443234323434543234432342343432342344344321233212312332123"
        "1233231012121254323432232344323423342123232223336543454334345334534422"
        "3343334444543453345342343441232233344432343234342343412332334332123212"
        "2312320",
        "9876543476543354323432333654323543233232343233233235432124321221223212"
        "2122122101110165432343223233432322233212121322227654345433334433433332"
        "2232433354654344334233232332121322433543234323233232321223233243212321"
        "12212110",
        "8765434565432343223212323543234321232232332231233234321232101211222112"
        "0122122123122354323432121233212312231012121212226543454323234323423321"
        "2232323343543343234233342332231232343432232123233232323221223232123101"
        "122121120",
        "9876543476543254322321222654323432123221243222122325432123210121123211"
        "1011213212211265432343212122321221122101110321117654345432323432322232"
        "1121432254654334323223231222120321434543223212223221232112132343212210"
        "1121102110",
        "9876543476543354323323434654323432343233443232343235432123212322333212"
        "1233123223232365432343232344322323232123232323335432343223123212323210"
        "1121212232654344334233233432122323233543233234343233332332312243212212"
        "23212222120",
        "5432345632123422345345656322345123453455623453455452123452345645662345"
        "4566453456565621234523454566234545453456565345553234563456567345656545"
        "6676456656334562345453454553455345455233453456563455545664556412345345"
        "563455454550",
        "6543234543212332234334545432234212342344522342344343212342234534551234"
        "3455342345454532123422343455123434342345454234444323452345456234545434"
        "5565345545323451234342343442344234344322342345452344434553445321234234"
        "4523443434410",
        "7654323454321243223333444543223321232233432231233234321233223433442123"
        "2344233234343443212332233344212323233234343223335432343234345323434323"
        "4454234434432342123232232331233123233432233234342233323442334232123223"
        "34123323233210",
        "8765432365432154322433344654322432123223343222122225432124322333343212"
        "2233124323332354321243223334321222124323332322326543234323334432323232"
        "3343323343543233212223221222122212323543224323333222232333233243212322"
        "332122323223210",
        "7654334554322332123223434543334322341233433342343344322342123423442234"
        "2344342345344543223421232344223423341234343123335433453234345334534423"
        "4454234434432342234232343442343233343321232234341233323443334232234123"
        "3423433423321120",
        "8765433465432243212322333654333432232122343332232335432233212322333223"
        "1233233234233454322332122233322312232123232212226543344323234433423332"
        "3343323343543233223123232332232222332432123223232122232332223143223212"
        "23223223122321110",
        "9876543376543254321432233765433543223212254333221336543224321232234322"
        "2122224323322365432243213223432221223212221321217654335432323543332343"
        "2232432254654324322214322223221321433543214322323212143223232254322321"
        "223221322134321210",
        "9876544476543354322321222765444543333221254443332446543334322321224333"
        "2232334334233465433343222122433322333223122322127654445433323544433443"
        "3233433254654334323224332333232322433543223212223221221222132254333322"
        "1233323222343222110",
        "7654323454321243223333444543223321232233432231233234321233223433442123"
        "2344233234343443212332233344212323232234343233435432343234345323434323"
        "4454234434432342123232232331233123233432333234342333323442334332123223"
        "34123323233210111220",
        "8765432365432154322433344654322432123223343222122225432124322333343212"
        "2233124323332354321243223334321222123223332322326543234323334432323232"
        "3343323343543233212223221222122212323543224323333222232333233243212322"
        "332122322223210211210",
        "9876543276543265432543344765432543214323354323212326543215432243344321"
        "3223215432433465432154324334432132214322332432327654325432434543232343"
        "2332432354654324321324322123212322433654325432434323243234343354321432"
        "3332124332343213212210",
        "9876543376543254321432233765433543223212254333221336543224321232234322"
        "2122224323322365432243213223432221223212221321217654335432323543332343"
        "2232432254654324322214322223221321433543214322323212132223232254322321"
        "22322132213432121012110",
        "8765434565432354323433444654334432343233443342343345432343212322333223"
        "1233232123232354323443233344323423342123232323336543454334345434534432"
        "3343334444543343234233343442342233343543233234343233323332334243234212"
        "232232121223212212212320",
        "9876543476543265432543344765433543234323354333232336543234321232234322"
        "2122223212221265432354324334432332233212221432327654345433434543433343"
        "2232433354654334323324332333231322434654324323334322232223243354323321"
        "2232212121343213212212110",
        "8765434565432343212322333654334432232122343332232335432343212322333223"
        "1233233234233454323432122233322312232123232212226543454323234433423332"
        "3343323343543233234123232333342332342432123223232122232332323143223212"
        "23323223122321210112121120",
        "9876543476543254323433444765433543233233454333233336543234323433444323"
        "2344234334343465432343233344432323233234343323335432343212223322312221"
        "2232212232654344323234332333233323333543234334343233343443323254323323"
        "343233332314321212221222210",
        "4321234521012311234234545211234012342344512342344342123451234534552345"
        "3455453456455610123412343455123434342345454234442123452345456234545434"
        "5565345545323451234342343443454234344332342345452344434553445323345345"
        "5634554545512343455345545450",
        "5432123432101221123223434321123101231233421231233233212342123423441234"
        "2344342345344521012311232344012323231234343123333212341234345123434323"
        "4454234434212340123231232332343123233321231234341233323442334232234234"
        "45234434344212323442344343410",
        "6543212343210132112222333432112210121122321120122124321233212322332123"
        "1233233234233432101221122233101212122123232212224321232123234212323222"
        "3343123323321231012122121221232012122432122123232122222331223143223323"
        "342233332333212223312332323210",
        "7654321254321043211322233543211321012112232111011215432124321232233212"
        "2122124323322343210132112223210111013212221321215432123212223321212132"
        "2232212232432122101112110112121101213543213212223211132222132254322432"
        "3332224332343213223212232323210",
        "6543223443211221012112323432223211230122332231232234322342123412332234"
        "2343342345344532112310121233112312231234233012224322342123234223423323"
        "4344123323321231123121232332343122232210121123230122212332223132123223"
        "34123323233322312332343342321120",
        "7654322354321132101211222543222321121011232221121225432233212321223223"
        "1232233234233443211221011122211201122123122101115432233212123322312232"
        "3233212232432122112012121222232111221321012112121011121222112043212322"
        "232122322224322212222322312321110",
        "8765432265432143210321122654322432112101143222110326543224321232124322"
        "2121224323322354321132102112321110113212211210106543224321212432221243"
        "2222321143543213211103211113221210322432103211212101032123221154321432"
        "3232124332354323212322132234321210",
        "8765433365432243211210111654333432222110143332221336543334322321214333"
        "2232334334233454322232111011322211223223122211016543334322212433322343"
        "3233322143543223212113221223232211322432112101112110121211021154322321"
        "22322132213543332213332332343222110",
        "6543212343210132112222333432112210121122321120122124321233212322332123"
        "1233233234233432101221122233101212122123232122324321232123234212323222"
        "3343123323321231012122121221232012122321222123231222223331223243233212"
        "232232231223212223312332323210111220",
        "7654321254321043211322233543211321012112232111011215432124321232233212"
        "2122124323322343210132112223210111013212221211215432123212223321212132"
        "2232212232432122101112110112121101212432113212222111132222122154322321"
        "2232213221343213223212232223210211210",
        "7654323454321243212322333543223321232122332231232234321232101211222112"
        "0122122123122343212332122233212312231012121212225432343223234323423321"
        "2232223333432232123123232332231122232432122123232122222221223132123101"
        "12212112011432321222232121232122122120",
        "8765432365432154321432233654322432123212243222121325432123210121123211"
        "1011213212211254321243213223321221122101110321216543234322323432322232"
        "1121322243543223212213221222120211323543213212223211132112132243212210"
        "112110211025432321232212123432132122110",
        "7654323454321232101211222543223321121011243222121325432343212321223223"
        "1232233234233443212321011122211201122123122101115432343212123322312232"
        "3233212232432122123012121223232221231321012112121011121222212043212212"
        "2321222212243222122323223123212101121120",
        "5432345632123422345345656322345123453455623453455453234562345645663456"
        "4566564567566721234523454566234545453456565345552123452345456234545434"
        "5565345545323452345453454554565345344433453456563455545664545434456345"
        "56456556455234545664566565512343455344540",
        "6543234543212332234334545432234212342344532342344344323453234534552345"
        "3455453456455632123422343455123434342345454234443212342234345123434323"
        "4454234434322341234342343443454234233432342345452344434553434343345234"
        "453454453443234345534554544212323442334310",
        "7654323454321243223333444543223321232233432231233235432344323433443234"
        "2344344345344543212332233344212323233234343323334321233223334212323232"
        "3343223323432232123233232332343123122543233234343233333442323254334323"
        "3433433423343233344234434333212223312232210",
        "8765432365432154322433344654322432123223343222122326543235432343344323"
        "3233235434433454321243223334321222124323332432325432124322334321222143"
        "2332322332543223212223221223232212213654324323334322243333232365433432"
        "33433243324543243343233434343213223213233210",
        "7654334554322332123223434543334322341233443342343345433453234523443345"
        "3454453456455643223421232344223423342345344123334322342123234223423323"
        "4344123323432342234232343443454233233321232234341233323443333243234334"
        "342344343434334234434544533322312332334221120",
        "8765433465432243212322333654333432232122343332232336543344323432334334"
        "2343344345344554322332122233322312233234233212225432233212223322312232"
        "3233212232543233223123232333343222222432123223232122232333222154323433"
        "2332334333354333233334334224322212222231321110",
        "9876544476543354322321222765444543333221254443332447654445433432325444"
        "3343445445344565433343222122433322334334233322126543334322212433322343"
        "3233322143654334323224332334343322323543223212223221232322121265433432"
        "33433243323654443324443443354333221333324322210",
        "7654323454321243223333444543223321232233432231233235432344323433443234"
        "2344344345344543212332233344212323233234343233434321233223334212323232"
        "3343233423432232123233232332343123122432333234342333334442323354344323"
        "343343342324323334423443433321222331223321011120",
        "8765432365432154322433344654322432123223343222122326543235432343344323"
        "3233235434433454321243223334321222124323332322325432124322334321222143"
        "2332322332543223212223221223232212213543224323333222243333232265433432"
        "3343324332354324334323343334321322321322321021210",
        "8765434565432354323433444654334432343233443342343345432343212322333223"
        "1233233234233454323443233344323423342123232323335432344323334323423321"
        "2232323333543343234234343443232233233543233234343233333332323243234212"
        "23323223121543432333343232243233233231223212212120",
        "8765434565432343212322333654334432232122354333232436543454323432334334"
        "2343344345344554323432122233322312233234233212225432343212223322312232"
        "3233212232543233223123232334343322332432123223232122232333323154323323"
        "233233332325433323343433422432321223223132121012110",
        "6543234543234533456456767432345234564566723454566453234561234534552345"
        "3455453456455621234523454566234545452345454345551012341234345123434323"
        "4454234434212342345452344543454345233323453456563455534554534443456234"
        "4534544534434563455456545442345456645344123434534440",
        "7654323454323443345445656543234323453455632343455344323452123423442234"
        "2344342345344532123422343455123434341234343234442101231123234012323212"
        "3343123323321232234341233432343234122432342345452344423443423332345123"
        "34234334233434523443454343332343455342332123234233310",
        "8765432365432354334444555654323432343344543232344235432343212322333223"
        "1233233234233443212332233344212323232123232323333210122112223101212121"
        "2232212212432123223332122322232123011543233234343233332332312243234212"
        "233232231225434323333432322432333442312232122231222210",
        "9876543276543265433544455765432543234334454323233326543234321232234322"
        "2122224323322354321243223334321222123212221432324321013211223210111032"
        "1221321221543214322333212213221212102654324323334322243223221354323321"
        "2232213221365434323433232335432433432213432132321333210",
        "8765433465432343234334545654334432342344543342344345433453223412333334"
        "2343343345344543223421232344223423342234233123333211231012123112312212"
        "3233012212432232123232232332343123122432343234342343412332322343345223"
        "23334323232543433433454343243232344232323223123233221120",
        "9876543376543254323433444765433543233233454333233336543344322321224333"
        "2232334334233454322332122233322312233223122212224321122101112211201121"
        "2122101121543223212223221223232212112543234323233232321223221254334322"
        "124332322226543433243433321543232333222143222122221321110",
        "8765432365432354334444555654323432343344543232344235432343212322333223"
        "1233233234233443212332233344212323232123232223333210122112223101212121"
        "2232122312432123223332122322232123011543233234343233323332312243234212"
        "2332322312154343233334323224323334423122321222312232101110",
        "9876543476543365434544555765434543344344554343344346543234323432334323"
        "2343233234122354323443233344323423342123232323334321233212223212312210"
        "1121212222543234323333232332122223122654344334344343432332312254323323"
        "23323323120654343434344342154334344332324323323231232122110",
        "5432123443223423345445656321234123453455612343455342123450123423441234"
        "2344342345344532334512343455234534451234343234442123452345456234545423"
        "4454345545212342345452344543453344343323452345453454523443445432345123"
        "342343342334345234434543434343434553423323454564534123434340",
        "6543212354322332334344555432123212342344521232344233212341012312332123"
        "1233231234233443223421232344123423340123232123333212342234345123434312"
        "3343234434321232234341233432342233232322341234342343412332334321234012"
        "2312322312232341233234323234323234423122323434534232123232310",
        "7654321265432243233334445543212321232233432121233124321232101211222112"
        "0122122123122354322332122233212312231012121212224321233223334212323221"
        "2232323323432123223332122323231222121432232123233232321221223232123101"
        "12212112011432321222232121243322233120114323334231232122212210",
        "7654322354321243223233444543223321231233432231233234322342112301223223"
        "1232232234233443212332231233212323231123122223234322342123234223423322"
        "3233123323432232123232232331232123232433332234231233301221223332234112"
        "122232121224323223223432323321222331212243232342323322312232110",
        "8765432265432154322323334654322432122122343222122225432233211210113222"
        "1121223223122354321243222122321212122112011322125432233212223322312232"
        "2122212232543223212223221222121212222543323223122122210112132243223211"
        "0132212111254323221323222224321322221112543232332224322212232110",
        "7654321265432243233334445543212321232233432121233124321232101211222112"
        "0122122123122354323332122233212312231012121212224321233223334212323221"
        "2232223323432123223332122322231232121432232123232232312221223232123101"
        "12212112011432321222232121243232233120114323334231232122212210110",
        "4321012332112322234334545210123112342344501232344233212341234534551234"
        "3455342345454532223423344455223434342345454344542123452345456234545434"
        "5565345545101231234341233432344234342212342345452344434553445332345234"
        "453454453444334345534554545432333442334434344453445234545451233430",
        "5432101243211232223333444321012211232233410121233124321232123423442123"
        "2344232234343443212332233344212323231234343233433212342234345123434323"
        "4454234434210121123230122321233123231321232234341233323442334232234123"
        "3423433423343232344234434343212223312233432333423343234343421223210",
        "6543210154321143222333344432101321122223321011122015432123212322333212"
        "1233123223232354321243223334321222122123232322324321233223334212323232"
        "3343323323321012112221011212122212120432123223332122232332223143223212"
        "23323223122543232333233232343213223211225432434322343233323321221210",
        "6543211243210132112222333432112210121122321120122124321233212312332123"
        "1233233234233432101221122233101212122123232222324321232123234212323222"
        "3343123323321121012121121221232012121432222123232222212331223243223223"
        "232233232333212223312332333210111220112232122231223432323233221222110",
        "6543210154321143222333344432101321122223321011122015432123212322333212"
        "1233123223232343212232233344212223222123232323334321233223334212323232"
        "3343233423321012112221011212122123120432123223332122222332323143212212"
        "232122221224322323322332323321222331212243233342323432333233212212101"
        "0",
        "5432123443223421234234545321234223452344512343454344323452345634552345"
        "4565453456565632334512343455234534453456455234443234562345456345645545"
        "6566345545212342345342344543455344453212342345452344434553445332345345"
        "5634554545543453455456556454334234434453444534545543456455623445412333"
        "0",
        "6543212354322332123223434432123322341233421232343235432343234523443234"
        "3454343345454543223421232344323423342345344123334323453234345234534434"
        "5455234434321232234231233432344233342321232234341233323442334243234234"
        "4523443434443342344345445343223123323342433423434434345344532334321222"
        "10",
        "7654321265432243212322333543212432232122332122232126543234323432334323"
        "2343234334343454322332122233322312233234233212225432344323234323423343"
        "4344323333432123223122122323233322231432123223232122232333223154323323"
        "3432333323354333233434334234322212232231543332343325434433443233232121"
        "210",
        "7654322354321243223212323543223321232232332231233235432344323423433234"
        "2344344345344543212332231233212323233234343223235432343234234323434333"
        "4454234334432232123232232332343123232432232123232232323431223254334323"
        "3433433423343233343234434343212223212232432333323335434343443323332212"
        "2110",
        "5432234532123410123123434432345212341233422342343343223451234523442345"
        "3454453456455621234501232344123423342345344123333234561234345234534434"
        "5455234434212342345232343443454343453101231234341233323442334221234234"
        "4523443434432342344345445343234123323342434523434434456344534444423444"
        "12330",
        "6543223443212321012112323432234211230122332231232234322342123412333234"
        "2343342345344532123410121233212312231234233012224323452123234223423323"
        "4344123323321232234121232332343232342210121123230122212331223132123223"
        "3412332323332231233234334232123012212231323412323324345233443333332333"
        "212210",
        "6543345643234521234234545432345323452344523453454453212342234534551234"
        "3455342345454532234512343455234534453345454234444334562345456345645534"
        "5565345545323453456343454552344344454212342345452344434553445321234234"
        "4523443434432343455345545454345234434343545634545445445344544344334454"
        "2344120",
        "7654334554323432123223434543234322341233432342343344321233223423442123"
        "2344233234343443223421232344323423342234343123335433453234345334534423"
        "4454234434432343345232343441233233343321232234341233323442334232123223"
        "3412332323343232344234434343234123323232434523434334334233443233243343"
        "32332110",
        "6543456743234532345345656321234223453455612343455342101231123423440123"
        "2344231234343432123422343455123434342234343334443223451234345234534423"
        "4454234434323452345452344541233234344212342345452344423443434310123123"
        "3412332323321232344234434343234345534233434534545344334233443233244343"
        "344523120"};
    int T;
    cin >> T;
    for (int t = 0; t < T; ++t) {
      int a, b;
      cin >> a >> b;
      vector<int> F, G;
      fact(a, F);
      fact(b, G);
      int i = IDX[F], j = IDX[G];
      if (i < j) swap(i, j);
      cout << (DIST[i][j] - '0') << '\n';
    }
  }
};
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  TaskD solver;
  std::istream& in(std::cin);
  std::ostream& out(std::cout);
  solver.solve(in, out);
  return 0;
}