#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC optimize("no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long N = 1e6 + 100, OO = 1e9 + 7, M = 1e9 + 7, P = 6151, T = 2e3,
                SQ = 280, lg = 30;
long long mfac[N], tt[N], t[N], lv[T], nfac[T], d[T][T], nbest[T], mbest[T];
map<long long, long long> s;
vector<vector<long long> > vv;
vector<long long> tfac;
long long v(long long x) {
  long long cx = x;
  tfac.clear();
  while (x > 1) {
    long long m = mfac[x];
    long long c = 0;
    while (x % m == 0) c++, x /= m;
    tfac.push_back(c);
  }
  sort(tfac.begin(), tfac.end());
  long long tot = 0;
  for (long long r : tfac) tot = 30 * tot + r;
  tt[cx] = tot;
  return tot;
}
vector<long long> decomp(long long x) {
  vector<long long> res;
  while (x) res.push_back(x % 30), x /= 30;
  return res;
}
long long gfac(long long x) {
  vector<long long> v = decomp(x);
  long long res = 1;
  for (long long cfac : v) res *= (cfac + 1);
  return res;
}
long long gfac(vector<long long> v) {
  long long res = 1;
  for (long long cfac : v) res *= (cfac + 1);
  return res;
}
long long cdist(vector<long long> &v1, vector<long long> &v2) {
  long long rr = 0;
  for (long long i = 0; i < max((long long)v1.size(), (long long)v2.size());
       i++) {
    long long l = 0;
    if (i < (long long)v1.size()) l = v1[i];
    long long r = 0;
    if (i < (long long)v2.size()) r = v2[i];
    rr += abs(l - r);
  }
  return rr;
}
long long cdist(long long x, long long y) {
  vector<long long> v1 = decomp(x), v2 = decomp(y);
  long long rr = 0;
  for (long long i = 0; i < max((long long)v1.size(), (long long)v2.size());
       i++) {
    long long l = 0;
    if (i < (long long)v1.size()) l = v1[i];
    long long r = 0;
    if (i < (long long)v2.size()) r = v2[i];
    rr += abs(l - r);
  }
  return rr;
}
void buildvv(vector<long long> vcur) {
  vv.push_back(vcur);
  long long hi = 1000;
  if (vcur.size()) hi = vcur.back();
  long long cprod = 1;
  for (long long vval : vcur) cprod *= (vval + 1);
  hi = min(hi, 1000 / cprod);
  while (hi) {
    vcur.push_back(hi);
    buildvv(vcur);
    vcur.pop_back();
    hi--;
  }
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for (long long i = 1; i < N; i++) mfac[i] = 1;
  for (long long i = 2; i < N; i++) {
    if (mfac[i] == 1) {
      mfac[i] = i;
      for (long long j = 2 * i; j < N; j += i) mfac[j] = i;
    }
  }
  for (long long i = 1; i < N; i++) {
    long long r = v(i);
    s[r];
  }
  vector<long long> empty;
  buildvv(empty);
  long long ntype = 0;
  for (auto it = s.begin(); it != s.end(); it++) {
    it->second = ntype;
    lv[ntype] = it->first;
    ntype++;
  }
  for (long long i = 1; i < N; i++) t[i] = s[tt[i]];
  long long fmax = 0;
  for (long long i = 0; i < ntype; i++) {
    for (long long j = 0; j < T; j++) d[i][j] = 1e9;
    vector<long long> itype = decomp(lv[i]);
    for (vector<long long> p : vv) {
      long long g = gfac(p);
      d[i][g] = min(d[i][g], cdist(itype, p));
    }
    nfac[i] = gfac(lv[i]);
    fmax = max(fmax, nfac[i]);
  }
  long long TT;
  cin >> TT;
  for (long long tst = 0; tst < TT; tst++) {
    long long a, b;
    cin >> a >> b;
    long long c1 = t[a], c2 = t[b];
    long long res = 1e9;
    for (long long i = 0; i < T; i++) res = min(res, d[c1][i] + d[c2][i]);
    cout << res << endl;
  }
}
