#include <bits/stdc++.h>
using namespace std;
template <class T>
inline void chkmax(T &a, T b) {
  if (a < b) a = b;
}
template <class T>
inline void chkmin(T &a, T b) {
  if (a > b) a = b;
}
inline int read() {
  int sum = 0, p = 1;
  char ch = getchar();
  while (!(('0' <= ch && ch <= '9') || ch == '-')) ch = getchar();
  if (ch == '-') p = -1, ch = getchar();
  while ('0' <= ch && ch <= '9') sum = sum * 10 + ch - 48, ch = getchar();
  return sum * p;
}
const int maxn = 4e3 + 20;
const int maxp = 1e8;
const int seed = 101;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int prime[12] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
int n;
vector<int> b[maxn];
int bl[maxn], hs[maxn];
int tot;
vector<int> to[maxn];
map<int, int> mp;
inline int GetHash(vector<int> now) {
  int hs = 0;
  for (int x : now) hs = ((long long)hs * seed + x) % mod;
  return hs;
}
void dfs(int u, vector<int> t, int ns, int lst, int All) {
  if (u > 8) return;
  b[++tot] = t;
  bl[tot] = ns;
  hs[tot] = GetHash(t);
  mp[hs[tot]] = tot;
  vector<int> v;
  for (int j = (1), _end_ = (min(lst, 22 - All)); j <= _end_; j++) {
    v = t;
    v.push_back(j);
    dfs(u + 1, v, ns * (j + 1), j, All + j);
  }
}
int sx[maxn];
int td;
vector<int> tod[maxn];
int dis[600][maxn];
queue<int> q;
inline void bfs() {
  for (int st = (1), _end_ = (td); st <= _end_; st++) {
    memset(dis[st], inf, sizeof(dis[st]));
    for (int v : tod[st]) dis[st][v] = 0, q.push(v);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (int v : to[u]) {
        if (dis[st][v] > dis[st][u] + 1) {
          dis[st][v] = dis[st][u] + 1;
          q.push(v);
        }
      }
    }
  }
}
inline void prepare() {
  dfs(1, {}, 1, 100, 0);
  for (int i = (1), _end_ = (tot); i <= _end_; i++) {
    vector<int> t;
    int len = b[i].size();
    for (int j = (0), _end_ = (len - 1); j <= _end_; j++) {
      t = b[i];
      t[j]++;
      sort(t.begin(), t.end(), [](int a, int b) { return a > b; });
      int hs = GetHash(t);
      if (mp.find(hs) == mp.end()) continue;
      int v = mp[GetHash(t)];
      to[i].push_back(v);
      to[v].push_back(i);
    }
    {
      t = b[i];
      t.push_back(1);
      int hs = GetHash(t);
      if (mp.find(hs) == mp.end()) continue;
      int v = mp[GetHash(t)];
      to[i].push_back(v);
      to[v].push_back(i);
    }
  }
  int t = 0;
  for (int i = (1), _end_ = (tot); i <= _end_; i++) sx[++t] = bl[i];
  sort(sx + 1, sx + t + 1);
  t = unique(sx + 1, sx + t + 1) - (sx + 1);
  td = t;
  for (int i = (1), _end_ = (tot); i <= _end_; i++)
    bl[i] = lower_bound(sx + 1, sx + t + 1, bl[i]) - (sx),
    tod[bl[i]].push_back(i);
  bfs();
}
inline int fj(int x) {
  vector<int> a;
  for (int i = 2; i * i <= x; i++)
    if (x % i == 0) {
      int s = 0;
      while (!(x % i)) x /= i, s++;
      a.push_back(s);
    }
  if (x > 1) a.push_back(1);
  sort(a.begin(), a.end(), [](int a, int b) { return a > b; });
  return mp[GetHash(a)];
}
inline void init() {
  int A = fj(read()), B = fj(read());
  int ans = inf;
  for (int i = (1), _end_ = (td); i <= _end_; i++)
    chkmin(ans, dis[i][A] + dis[i][B]);
  printf("%d\n", ans);
}
int main() {
  prepare();
  int t = read();
  while (t--) {
    init();
  }
  return 0;
}
