#include <bits/stdc++.h>
const int maxn = 2e5 + 17;
int vis[maxn], sz, s[maxn], u, v, n, q, dis[maxn], val[maxn], D[maxn * 5],
    p[maxn];
std::vector<int> ch[maxn];
std::map<std::vector<int>, int> G;
int d[6005][905];
void dfs(int u, int sum, int lim) {
  std::vector<int> v;
  for (int i = 1; i < u; ++i) v.push_back(s[i]);
  std::sort(v.begin(), v.end());
  G[v] = ++sz;
  for (int i = lim; sum + i <= 22; ++i) {
    s[u] = i;
    dfs(u + 1, sum + i, std::max(i, lim));
  }
}
void bfs(int x) {
  vis[x] = 1;
  std::memset(dis, 63, sizeof(dis));
  std::memset(d[x], 63, sizeof(d[x]));
  std::queue<int> q;
  q.push(x);
  dis[x] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    d[x][val[u]] = std::min(d[x][val[u]], dis[u]);
    for (int v : ch[u]) {
      if (dis[v] > dis[u] + 1) {
        dis[v] = dis[u] + 1;
        q.push(v);
      }
    }
  }
}
int inc(std::vector<int> v, int p) {
  v[p]++;
  std::sort(v.begin(), v.end());
  return G[v];
}
int dec(std::vector<int> v, int p) {
  v[p]--;
  std::sort(v.begin(), v.end());
  while (v.size() && v.front() == 0) v.erase(v.begin());
  return G.count(v) ? G[v] : 0;
}
int get_id(int x) {
  std::vector<int> v;
  int z = x;
  while (z != 1) {
    int y = D[z], c = 0;
    while (z % y == 0) {
      c++;
      z /= y;
    }
    v.push_back(c);
  }
  std::sort(v.begin(), v.end());
  return G.count(v) ? G[v] : 0;
}
int main() {
  dfs(1, 0, 1);
  int t1 = 1;
  std::vector<std::pair<std::vector<int>, int> > W;
  for (auto x : G) W.push_back({x.first, x.second});
  for (auto x : W) {
    std::vector<int> v = x.first;
    int id = x.second;
    val[id] = 1;
    for (int z : v) {
      val[id] *= (z + 1);
    }
    for (int i = 0; i < v.size(); ++i) {
      int z = inc(v, i);
      if (z) ch[id].push_back(z);
      z = dec(v, i);
      if (z) ch[id].push_back(z);
    }
    v.insert(v.begin(), 1);
    if (G.count(v)) ch[id].push_back(G[v]);
    std::sort(ch[id].begin(), ch[id].end());
    std::unique(ch[id].begin(), ch[id].end());
    p[++t1] = val[id];
  }
  std::sort(p + 1, p + t1 + 1);
  t1 = std::unique(p + 1, p + t1 + 1) - (p + 1);
  for (int i = 1; i <= sz; ++i)
    val[i] = std::lower_bound(p + 1, p + t1 + 1, val[i]) - (p + 1) + 1;
  const int lim = 1e6;
  for (int i = 2; i <= lim; ++i) {
    if (!D[i]) {
      for (int j = i; j <= lim; j += i) D[j] = i;
    }
  }
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &u, &v);
    int a = get_id(u), b = get_id(v);
    if (!vis[a]) bfs(a);
    if (!vis[b]) bfs(b);
    int ans = 1e9;
    for (int i = 1; i <= t1; ++i) ans = std::min(ans, d[a][i] + d[b][i]);
    printf("%d\n", ans);
  }
  return 0;
}
