#include <bits/stdc++.h>
const int MAXN = 1000000 + 10;
int prime[MAXN], p_cnt;
bool np[MAXN];
int val[MAXN];
int pa[MAXN], pb[MAXN], cnt1, cnt2;
int dis[500][1000];
int n = 1e6;
void dfs(int x, int step, int t, int p, int max1, int max2) {
  if (!pa[t]) pa[t] = ++cnt1;
  if (!pb[p]) pb[p] = ++cnt2;
  if (step > dis[pa[t]][pb[p]]) return;
  if (x > 7) {
    dis[pa[t]][pb[p]] = step;
    return;
  }
  for (int i = 0; i <= max1 && t <= 1000000; i++) {
    for (int j = std::max(0, i - (10 - step));
         j <= std::min(max2, i + (10 - step)); j++) {
      dfs(x + 1, step + std::abs(i - j), t, p * (j + 1), i, j);
    }
    t *= prime[x];
  }
}
void init() {
  for (int i = 2; i <= 1000; i++) {
    if (!np[i]) prime[++p_cnt] = i;
    for (int j = 1; j <= p_cnt && prime[j] * i <= 1000; j++) {
      np[prime[j] * i] = 1;
      if (i % prime[j] == 0) break;
    }
  }
  static int f[MAXN];
  static std::vector<int> v[MAXN];
  for (int i = 1; i <= n; i++) {
    f[i] = i;
  }
  for (int i = 1; i <= p_cnt; i++) {
    int x = prime[i];
    for (int j = x; j <= n; j += x) {
      int cnt = 0;
      while (f[j] % x == 0) {
        f[j] /= x;
        cnt++;
      }
      v[j].push_back(cnt);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (f[i] != 1) v[i].push_back(1);
    std::sort(v[i].begin(), v[i].end(), std::greater<int>());
    val[i] = 1;
    for (int j = 0; j < (int)v[i].size(); j++) {
      for (int t = 1; t <= v[i][j]; t++) {
        val[i] *= prime[j + 1];
      }
    }
  }
  memset(dis, 63, sizeof dis);
  dfs(1, 0, 1, 1, 20, 20);
}
int main() {
  init();
  fprintf(stderr, "!\n");
  int t;
  scanf("%d", &t);
  static int ans[500][500];
  memset(ans, -1, sizeof ans);
  while (t--) {
    int a, b;
    scanf("%d%d", &a, &b);
    a = pa[val[a]], b = pa[val[b]];
    if (a > b) std::swap(a, b);
    if (ans[a][b] != -1) {
      printf("%d\n", ans[a][b]);
      continue;
    }
    ans[a][b] = 100;
    for (int i = 1; i <= cnt2; i++) {
      ans[a][b] = std::min(ans[a][b], dis[a][i] + dis[b][i]);
    }
    printf("%d\n", ans[a][b]);
  }
}
