#include <bits/stdc++.h>
using namespace std;
const double PI = 2 * acos(0.0);
template <class T>
void show(T a) {
  for (auto x : a) cout << x << " ";
  cout << endl;
}
const string DIGITS = "0123456789";
const string ALPH = "abcdefghijklmnopqrstuvwxyz";
const int N = 1e6 + 1;
int mn[N];
void fact(int n, vector<int> &f) {
  f.push_back(mn[n]);
  if (n == mn[n]) return;
  fact(n / mn[n], f);
}
const int oo = 1e9 + 9;
vector<int> get_keks(int i) {
  vector<int> cur;
  if (i == 1) return cur;
  fact(i, cur);
  vector<int> keks;
  int prev = -1;
  for (auto x : cur) {
    if (x == prev)
      keks.back()++;
    else
      keks.push_back(1);
    prev = x;
  }
  sort(keks.begin(), keks.end());
  return keks;
}
const int BOUND = 8;
const int BOUND2 = 250;
void bfs(vector<int> s, map<long long, int> &res) {
  map<vector<int>, int> dp;
  dp[s] = 0;
  queue<vector<int>> q;
  q.push(s);
  while (!q.empty()) {
    vector<int> v = q.front();
    q.pop();
    if (dp[v] >= BOUND) break;
    long long lol = 1;
    for (auto x : v) lol *= (x + 1);
    if (lol >= BOUND2) continue;
    for (int i = 0; i < ((int)(v.size())); ++i) {
      vector<int> nx = v;
      nx[i]++;
      sort(nx.begin(), nx.end());
      if (!dp.count(nx)) {
        dp[nx] = dp[v] + 1;
        q.push(nx);
      }
      nx = v;
      nx[i]--;
      sort(nx.begin(), nx.end());
      reverse(nx.begin(), nx.end());
      while (nx.size() && nx.back() == 0) nx.pop_back();
      reverse(nx.begin(), nx.end());
      if (!dp.count(nx)) {
        dp[nx] = dp[v] + 1;
        q.push(nx);
      }
    }
    vector<int> nx = v;
    nx.push_back(1);
    sort(nx.begin(), nx.end());
    if (!dp.count(nx)) {
      dp[nx] = dp[v] + 1;
      q.push(nx);
    }
  }
  for (auto x : dp) {
    long long num = 1;
    for (auto y : x.first) num *= (y + 1);
    if (res.count(num)) x.second = min(x.second, (res[num]));
    res[num] = x.second;
  }
}
map<vector<int>, map<long long, int>> precalc;
void add(vector<int> v) {
  if (precalc.count(v)) return;
  map<long long, int> first;
  bfs(v, first);
  precalc[v] = first;
}
map<pair<vector<int>, vector<int>>, int> memget;
int get(vector<int> v, vector<int> u) {
  if (v > u) swap(u, v);
  if (memget.count({v, u})) return memget[{v, u}];
  add(v);
  add(u);
  int ans = oo;
  for (auto x : precalc[v]) {
    int cur = oo;
    if (precalc[u].count(x.first)) cur = x.second + precalc[u][x.first];
    ans = min(ans, (cur));
  }
  return memget[{v, u}] = ans;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  mn[1] = 1;
  for (int i = 2; i < N; ++i)
    if (!mn[i])
      for (int j = i; j < N; j += i)
        if (!mn[j]) mn[j] = i;
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    vector<int> ka = get_keks(a);
    vector<int> kb = get_keks(b);
    cout << get(ka, kb) << "\n";
  }
}
