#include <bits/stdc++.h>
using namespace std;
long long modpow(long long a, long long b,
                 long long mod = (long long)(1e9 + 7)) {
  if (!b) return 1;
  a %= mod;
  return modpow(a * a % mod, b / 2, mod) * (b & 1 ? a : 1) % mod;
}
const int maxn = 1000001;
const int sz = 30;
int p = 0;
map<vector<int>, int> state;
vector<vector<int> > inv;
map<int, vector<int> > adj;
map<int, vector<int> > bfs;
int sieve[maxn];
void init(vector<int> a) {
  state[vector<int>(a)] = p;
  inv.push_back(vector<int>(a));
  adj[p++] = vector<int>();
}
void addEdge(vector<int> &a, vector<int> &b) {
  if (!state.count(a)) init(a);
  if (!state.count(b)) init(b);
  adj[state[a]].push_back(state[b]);
  adj[state[b]].push_back(state[a]);
}
int eval(vector<int> &a) {
  int ans = 1;
  for (int i = 0; i < sz; i++) ans *= (a[i] + 1);
  return ans;
}
void recurse(int product, int sum, int i, int ls, vector<int> vec) {
  if (product > 300 || sum > sz) return;
  if (i == vec.size()) {
    vector<int> cpy(vec);
    if (!state.count(cpy)) init(cpy);
    for (int i = 0; i < vec.size(); i++) {
      if (!i || (vec[i] != vec[i - 1])) {
        cpy[i]++;
        if (vec[i]) addEdge(cpy, vec);
        cpy[i]--;
      }
      if (i == vec.size() - 1 || (vec[i] != vec[i + 1])) {
        cpy[i]--;
        if (vec[i]) addEdge(cpy, vec);
        cpy[i]++;
      }
    }
  } else {
    vec[i] = 0;
    recurse(product, sum, i + 1, 0, vec);
    for (int j = 1; j <= ls; j++) {
      vec[i] = j;
      recurse(product * (j + 1), sum + j, i + 1, j, vec);
    }
  }
}
void perform_bfs(int a) {
  bfs[a] = vector<int>(1000, 1000);
  int dist[p];
  memset(dist, 1000, sizeof(dist));
  dist[a] = 0;
  bool vis[p];
  memset(vis, false, sizeof(vis));
  vis[a] = true;
  queue<int> pq;
  pq.push(a);
  while (!pq.empty()) {
    int v = pq.front();
    pq.pop();
    (bfs[a][eval(inv[v])]) = min((bfs[a][eval(inv[v])]), (dist[v]));
    for (int w : adj[v])
      if (!vis[w]) {
        vis[w] = true;
        pq.push(w);
        dist[w] = dist[v] + 1;
      }
  }
}
int getans(int a, int b) {
  if (!bfs.count(a)) perform_bfs(a);
  if (!bfs.count(b)) perform_bfs(b);
  int ans = 100000;
  for (int i = 0; i < 300; i++) (ans) = min((ans), (bfs[a][i] + bfs[b][i]));
  return ans;
}
int convert(int a) {
  vector<int> ans;
  while (a > 1) {
    int p = sieve[a];
    int cnt = 0;
    while (a % p == 0) {
      a /= p;
      cnt++;
    }
    ans.push_back(cnt);
  }
  sort(ans.begin(), ans.end(), greater<int>());
  while (ans.size() < sz) ans.push_back(0);
  return state[ans];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  vector<int> ans(sz);
  recurse(1, 0, 0, sz, ans);
  memset(sieve, 0, sizeof(sieve));
  for (int i = 2; i <= maxn; i++) {
    if (!sieve[i]) {
      sieve[i] = i;
      for (int j = 2 * i; j < maxn; j += i) sieve[j] = i;
    }
  }
  int t;
  scanf("%d", &t);
  stringstream ss;
  for (int _ = 0; _ < t; _++) {
    int a, b;
    scanf("%d", &a);
    scanf("%d", &b);
    cout << getans(convert(a), convert(b)) << endl;
  }
  cout << ss.str() << endl;
  return 0;
}
