#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 50, P = 1e6, M = 300;
int q, x, y, na, nb, vis[N], id[N], pr[7] = {2, 3, 5, 7, 11, 13, 17}, a[N],
                                    b[N], dis[M][900], ans[M][M];
vector<int> f[N];
void dfs(int t, int v, int x, int y, int c1, int c2) {
  if (!a[x]) a[x] = ++na;
  if (!b[y]) b[y] = ++nb;
  if (dis[a[x]][b[y]] <= v) return;
  if (t == 7) {
    dis[a[x]][b[y]] = v;
    return;
  }
  for (int i = 0; i <= c1; i++)
    if (x <= P) {
      for (int j = 0; j <= c2; j++)
        if (v + abs(i - j) <= 10)
          dfs(t + 1, v + abs(i - j), x, y * (j + 1), i, j);
      x *= pr[t];
    }
}
int main() {
  for (int i = 2; i <= P; i++)
    if (!vis[i])
      for (int j = i; j <= P; j += i) {
        int t = j, c = 0;
        vis[j] = 1;
        while (t % i == 0) t /= i, c++;
        f[j].push_back(c);
      }
  for (int i = 1; i <= P; i++) {
    sort(f[i].begin(), f[i].end());
    reverse(f[i].begin(), f[i].end());
    id[i] = 1;
    for (int j = 0; j < f[i].size(); j++)
      for (int k = 0; k < f[i][j]; k++) id[i] *= pr[j];
  }
  memset(dis, 50, sizeof(dis));
  dfs(0, 0, 1, 1, 20, 20);
  scanf("%d", &q);
  while (q--) {
    scanf("%d%d", &x, &y);
    x = a[id[x]];
    y = a[id[y]];
    if (x > y) swap(x, y);
    if (x == y || ans[x][y]) {
      printf("%d\n", ans[x][y]);
      continue;
    }
    ans[x][y] = 100;
    for (int i = 1; i <= nb; i++)
      ans[x][y] = min(ans[x][y], dis[x][i] + dis[y][i]);
    printf("%d\n", ans[x][y]);
  }
  return 0;
}
