#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e15;
const int maxn = 1000005;
const int maxys = 500;
int n, m, i, j, t, k, s, pr[maxn], tot, stat, fa[maxn], typ[2005];
int pw[51][21];
bool vis[maxn];
map<vector<int>, int> mp;
vector<int> bac[2005];
inline int Min(int x, int y) { return x < y ? x : y; }
inline int Max(int x, int y) { return x > y ? x : y; }
bool cmp(int x, int y) { return x > y; }
inline int trans(int x) {
  vector<int> nw;
  nw.clear();
  while (x > 1) {
    int tmp = fa[x], tt = 0;
    while (x % tmp == 0) x /= tmp, ++tt;
    nw.push_back(tt);
  }
  sort(nw.begin(), nw.end(), cmp);
  return mp[nw];
}
inline bool jud(int *a, int ta) {
  int s = 0;
  long long yss = 1;
  for (int i = 1; i <= ta; ++i) {
    s += a[i];
    yss *= (a[i] + 1);
    if (s > 29 || yss > maxys) return 0;
  }
  sort(a + 1, a + ta + 1, cmp);
  s -= 10;
  long long now = 1;
  for (int i = 1; i <= ta && s; ++i) {
    int mu;
    if (s > a[i])
      now *= pw[i][a[i]], s -= a[i];
    else
      now *= pw[i][s], s = 0;
    if (now >= n) return 0;
  }
  return 1;
}
inline int get_ys(vector<int> vc) {
  int sz = vc.size(), ret = 1;
  for (int i = 0; i < sz; ++i) ret *= (vc[i] + 1);
  return ret;
}
void dfs1(int x, int nw, int lim, vector<int> vc) {
  mp[vc] = ++stat;
  bac[stat] = vc;
  x *= pr[nw];
  typ[stat] = get_ys(vc);
  vc.push_back(0);
  for (int i = 1; i <= lim && x < n; ++i, x *= pr[nw]) {
    vc[nw - 1]++;
    dfs1(x, nw + 1, i, vc);
  }
}
int d2a[30];
void dfs2(int nw, int lim, vector<int> vc) {
  if (!mp[vc]) {
    mp[vc] = ++stat;
    bac[stat] = vc;
    typ[stat] = get_ys(vc);
  }
  vc.push_back(0);
  for (int i = 1; i <= lim; ++i) {
    d2a[nw] = i;
    if (!jud(d2a, nw)) break;
    vc[nw - 1]++;
    dfs2(nw + 1, i, vc);
  }
}
int dis[290][2005], d2[290][maxys + 2];
queue<int> Q;
void bfs(int sta) {
  Q.push(sta);
  dis[sta][sta] = 0;
  while (!Q.empty()) {
    int x = Q.front();
    Q.pop();
    d2[sta][typ[x]] = Min(d2[sta][typ[x]], dis[sta][x]);
    vector<int> tmp;
    int nxt;
    tmp = bac[x];
    int sz = tmp.size();
    for (int i = 0; i < sz; ++i) {
      bool flg = (i == 0 ? 1 : tmp[i - 1] > tmp[i]);
      if (flg) {
        tmp[i]++;
        nxt = mp[tmp];
        if (nxt && dis[sta][nxt] > dis[sta][x] + 1) {
          dis[sta][nxt] = dis[sta][x] + 1;
          Q.push(nxt);
        }
        tmp[i]--;
      }
    }
    tmp.push_back(1);
    nxt = mp[tmp];
    if (nxt && dis[sta][nxt] > dis[sta][x] + 1) {
      dis[sta][nxt] = dis[sta][x] + 1;
      Q.push(nxt);
    }
    tmp.erase(--tmp.end());
    for (int i = 0; i < sz - 1; ++i) {
      bool flg = (tmp[i] > tmp[i + 1]);
      if (flg) {
        tmp[i]--;
        nxt = mp[tmp];
        if (nxt && dis[sta][nxt] > dis[sta][x] + 1) {
          dis[sta][nxt] = dis[sta][x] + 1;
          Q.push(nxt);
        }
        tmp[i]++;
      }
    }
    if (!sz) continue;
    tmp[sz - 1]--;
    if (!tmp[sz - 1]) tmp.erase(--tmp.end());
    nxt = mp[tmp];
    if (nxt && dis[sta][nxt] > dis[sta][x] + 1) {
      dis[sta][nxt] = dis[sta][x] + 1;
      Q.push(nxt);
    }
  }
}
int main() {
  n = 1000001;
  for (i = 2; i < n; ++i) {
    if (!vis[i]) {
      pr[++tot] = i;
      fa[i] = i;
    }
    for (j = 1; j <= tot && pr[j] * i < n; ++j) {
      vis[i * pr[j]] = 1;
      fa[i * pr[j]] = pr[j];
      if (i % pr[j] == 0) break;
    }
  }
  for (i = 1; i <= 50; ++i) {
    pw[i][0] = 1;
    for (j = 1; j <= 20; ++j) pw[i][j] = min(pw[i][j - 1] * pr[i], n);
  }
  dfs1(1, 1, 19, vector<int>());
  dfs2(1, 29, vector<int>());
  memset(dis, 0x3f3f3f3f, sizeof(dis));
  memset(d2, 0x3f3f3f3f, sizeof(d2));
  for (i = 1; i <= 289; ++i) {
    bfs(i);
  }
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d", &t, &k);
    t = trans(t);
    k = trans(k);
    s = 100;
    for (i = 1; i <= maxys; ++i) {
      s = Min(d2[t][i] + d2[k][i], s);
    }
    printf("%d\n", s);
  }
  return 0;
}
