#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chmin(T &x, const T &y) {
  if (x > y) x = y;
}
const int pr[] = {2, 3, 5, 7, 11, 13, 17};
const int N = 1e6 + 5, S = 300, T = 920;
int dy[N], dys[N], dyt[N], scnt, tcnt, dis[S][T];
int r[N];
int mxt;
void dfs(int h, int d, int s, int t, int ms, int mt) {
  if (!dys[s]) dys[s] = ++scnt;
  if (!dyt[t]) dyt[t] = ++tcnt;
  mxt = max(t, mxt);
  if (h == 7) {
    chmin(dis[dys[s]][dyt[t]], d);
    return;
  }
  for (int i = 0; s <= 1000000 && i <= ms; ++i, s *= pr[h])
    for (int j = 0; j <= mt; ++j)
      if (d + abs(i - j) <= 10)
        dfs(h + 1, d + abs(i - j), s, t * (j + 1), i, j);
}
int main() {
  for (int i = 0; i <= S - 1; ++i)
    for (int j = 0; j <= T - 1; ++j) dis[i][j] = 100;
  dfs(0, 0, 1, 1, 100, 100);
  cerr << scnt << " " << tcnt << " " << mxt << endl;
  for (int i = 1; i <= 1e6; ++i) {
    if (i > 1 && !r[i])
      for (int j = i; j <= 1e6; j += i) r[j] = i;
    vector<int> a;
    int x = i;
    while (x > 1) {
      int p = r[x], e = 0;
      while (x % p == 0) {
        x /= p;
        ++e;
      }
      a.push_back(e);
    }
    sort(a.begin(), a.end(), greater<int>());
    int ans = 1;
    for (int i = 0; i <= int(a.size()) - 1; ++i)
      for (int j = 1; j <= a[i]; ++j) ans *= pr[i];
    dy[i] = dys[ans];
  }
  int m;
  cin >> m;
  while (m--) {
    int a, b;
    scanf("%d%d", &a, &b);
    int ans = 100;
    for (int i = 1; i <= tcnt; ++i) chmin(ans, dis[dy[a]][i] + dis[dy[b]][i]);
    printf("%d\n", ans);
  }
}
