#include <bits/stdc++.h>
using namespace std;
const int MaxN = 1000000;
int p[MaxN + 5], prime[MaxN + 5], primes, a[21], a_cnt;
int zhuan(int x) {
  for (int i = 1; i <= a_cnt; ++i) a[i] = 0;
  a_cnt = 0;
  while (x != 1) {
    ++a_cnt;
    a[a_cnt] = 1;
    while (p[x] == p[x / p[x]]) {
      ++a[a_cnt];
      x /= p[x];
    }
    x /= p[x];
  }
  sort(a + 1, a + 1 + a_cnt, greater<int>());
  int val = 1;
  for (int i = 1; i <= a_cnt; ++i)
    for (int j = 0; j < a[i]; ++j) val *= prime[i];
  return val;
}
int T;
int cnt, id[MaxN + 5], Ans[501][501];
vector<pair<int, int> > pp[1001];
vector<pair<int, int> > Tmp;
void dfs(int t, int res, int num, int lim) {
  int flag = 0;
  if (t > a_cnt) {
    Tmp.push_back(pair<int, int>(num, 9 - res));
    flag = 1;
    lim = max(lim, 1);
    if (res <= lim) return;
  }
  for (int i = -res; i <= res; ++i)
    if (abs(i) >= lim && a[t] + i >= 0) {
      dfs(t + 1, res - abs(i), num * (a[t] + i + 1), flag ? i : 0);
    }
}
int main() {
  for (int i = 1; i <= MaxN; ++i) p[i] = i;
  for (int i = 2; i <= MaxN; ++i) {
    if (p[i] == i) prime[++primes] = i;
    for (int j = 1; j <= primes && prime[j] <= p[i] && prime[j] <= MaxN / i;
         ++j)
      p[i * prime[j]] = prime[j];
  }
  for (int i = 1; i <= 1000000; ++i) {
    int x = zhuan(i);
    if (!id[x]) {
      Tmp.clear();
      id[x] = ++cnt;
      dfs(1, 9, 1, 0);
      sort(Tmp.begin(), Tmp.end());
      for (int i = 0; i < (int)Tmp.size(); ++i) {
        pp[cnt].push_back(Tmp[i]);
        int j;
        for (j = i; j + 1 < (int)Tmp.size() && Tmp[j + 1].first == Tmp[j].first;
             ++j)
          ;
        i = j;
      }
    }
  }
  for (int i = 1; i <= cnt; ++i)
    for (int j = i + 1; j <= cnt; ++j) {
      int x = i, y = j, tx = 0, ty = 0, ans = 1000;
      while (tx < (int)pp[x].size() && ty < (int)pp[y].size()) {
        if (pp[x][tx].first < pp[y][ty].first)
          ++tx;
        else if (pp[y][ty].first < pp[x][tx].first)
          ++ty;
        else {
          ans = min(ans, pp[x][tx].second + pp[y][ty].second);
          ++tx;
          ++ty;
        }
      }
      Ans[x][y] = Ans[y][x] = ans;
    }
  scanf("%d", &T);
  while (T--) {
    int x, y;
    scanf("%d%d", &x, &y);
    x = id[zhuan(x)];
    y = id[zhuan(y)];
    printf("%d\n", Ans[x][y]);
  }
  return 0;
}
