#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int C = 26;
void add(int &x, int y) {
  x += y;
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
}
int fix(int x) {
  while (x >= MOD) x -= MOD;
  while (x < 0) x += MOD;
  return x;
}
int pw(int a, int b) {
  int ret = 1;
  while (b) {
    if (b & 1) ret = 1ll * ret * a % MOD;
    b >>= 1;
    a = 1ll * a * a % MOD;
  }
  return ret;
}
const int MAXN = 1e6 + 10;
vector<int> vec[MAXN];
bool seive[MAXN];
void build() {
  for (int i = 2; i < MAXN; i++) {
    if (!seive[i]) {
      vec[i].push_back(1);
      for (int j = 2 * i; j < MAXN; j += i) {
        int jj = j, cnt = 0;
        while (jj % i == 0) {
          ++cnt;
          jj /= i;
        }
        vec[j].push_back(cnt);
        seive[j] = 1;
      }
    }
    sort(vec[i].rbegin(), vec[i].rend());
  }
}
const int MAXP = 10;
const int MAXD = 333;
vector<int> fix(vector<int> v) {
  sort(v.rbegin(), v.rend());
  while (!v.empty() && v.back() == 0) v.pop_back();
  return v;
}
int eval(const vector<int> &v) {
  int r = 1;
  for (int x : v) r *= x + 1;
  return r;
}
vector<int> qu[MAXN];
int sz;
set<vector<int>> st;
void consider(const vector<int> &v) {
  if ((int)v.size() >= MAXP) return;
  if (eval(v) >= MAXD) return;
  if (!st.count(v)) {
    qu[sz++] = v;
    st.insert(v);
  }
}
map<vector<int>, array<int, MAXD>> d;
void bfs(int A) {
  if (d.count(vec[A])) return;
  array<int, MAXD> &dist = d[vec[A]];
  dist.fill(-1);
  sz = 0;
  st.clear();
  dist[eval(vec[A])] = 0;
  consider(vec[A]);
  int cur = 0;
  for (int i = 0; i < sz; ++cur) {
    int tt = sz;
    for (; i < tt; i++) {
      vector<int> u = qu[i];
      int dd = eval(u);
      if (dist[dd] == -1) dist[dd] = cur;
      vector<int> v = u;
      v.push_back(1);
      consider(fix(v));
      for (int &x : u) {
        --x;
        v = u;
        consider(fix(v));
        x += 2;
        v = u;
        consider(fix(v));
        --x;
      }
    }
  }
}
void solve() {
  if (vec[2].empty()) {
    build();
  }
  int A, B;
  cin >> A >> B;
  bfs(A);
  bfs(B);
  int ans = 69;
  array<int, MAXD> da = d[vec[A]], db = d[vec[B]];
  for (int v = 1; v < MAXD; v++) {
    if (~da[v] && ~db[v]) {
      ans = min(ans, da[v] + db[v]);
    }
  }
  cout << ans << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int te = 1;
  cin >> te;
  for (int w = 1; w <= te; w++) {
    solve();
  }
  return 0;
}
