#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10, M = 512;
const int p[] = {2, 3, 5, 7, 11, 13, 17};
map<int, int> exi, id;
int vcnt;
int b[20];
int Hash() {
  int ans = 0;
  for (int i = 0; i < 7; i++) ans = ans * 20 + b[i];
  return ans;
}
void dfs1(int cur, int mul, int lim) {
  if (cur == 7) {
    int ha = Hash();
    id[ha] = ++vcnt;
    exi[vcnt] = ha;
    return;
  }
  for (int i = 0; i <= lim; i++) {
    b[cur] = i;
    dfs1(cur + 1, mul, i);
    if (mul * p[cur] > N) break;
    mul *= p[cur];
  }
}
int dis[M * 3][M + 10];
void solve(int cur, int d, int lim) {
  if (cur == 7) {
    for (int i = 1; i <= vcnt; i++) {
      int val = exi[i], ans = 0;
      for (int j = 6; j >= 0; j--) {
        ans += abs(b[j] - (val % 20));
        val /= 20;
      }
      dis[d][i] = min(dis[d][i], ans);
    }
    return;
  }
  for (int i = 0; i <= lim; i++) {
    if (d * (i + 1) > M) break;
    b[cur] = i;
    solve(cur + 1, d * (i + 1), i);
  }
}
int get(int x) {
  memset(b, 0, sizeof b);
  int len = 0;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      while (x % i == 0) {
        x /= i;
        ++b[len];
      }
      len++;
    }
  }
  if (x != 1) b[len++] = 1;
  sort(b, b + 7);
  reverse(b, b + 7);
  int ans = Hash();
  return id[ans];
}
int T, A, B;
int main() {
  memset(dis, 0x3f, sizeof dis);
  dfs1(0, 1, 20);
  solve(0, 1, 20);
  cin >> T;
  while (T--) {
    cin >> A >> B;
    A = get(A), B = get(B);
    int ans = N;
    for (int i = 0; i <= M; i++) ans = min(ans, dis[i][A] + dis[i][B]);
    cout << ans << endl;
  }
  return 0;
}
