#include <bits/stdc++.h>
using namespace std;
inline bool isp(int x) {
  if (x <= 1) return 0;
  for (int i = 2; i * i <= x; i++) {
    if (x % i == 0) {
      return 0;
    }
  }
  return 1;
}
const int N = 1000000 + 5;
vector<vector<int>> a, b;
vector<int> cnt, aux, gen_primes;
vector<int> cntd;
inline void buildA(int i, int cur, int ant) {
  a.push_back(aux);
  for (int t = 1; t <= ant; t++) {
    if (cur * gen_primes[i] >= N) break;
    cur *= gen_primes[i];
    aux.push_back(t);
    buildA(i + 1, cur, t);
    aux.pop_back();
  }
}
inline void buildB(int cur, int ant) {
  b.push_back(aux);
  for (int t = 1; t <= ant; t++) {
    if (cur * (t + 1) > 1000) break;
    aux.push_back(t);
    buildB(cur * (t + 1), t);
    aux.pop_back();
  }
}
int ans[290][1005];
int best[290][290];
bool p[N];
vector<int> gr[N];
int rofl[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  for (int i = 1; i <= 1000; i++) {
    if (isp(i)) {
      gen_primes.push_back(i);
    }
  }
  buildA(0, 1, 1000);
  buildB(1, 1000);
  for (auto x : b) {
    int ans = 1;
    for (auto y : x) ans *= (y + 1);
    cntd.push_back(ans);
  }
  for (int i = 0; i < a.size(); i++) {
    for (int j = 1; j <= 1000; j++) ans[i][j] = 1e9;
    for (int j = 0; j < b.size(); j++) {
      int mx = max(a[i].size(), b[j].size()), sum = 0;
      for (int t = 0; t < mx; t++) {
        int add = 0;
        if (t < a[i].size()) add += a[i][t];
        if (t < b[j].size()) add -= b[j][t];
        sum += abs(add);
      }
      ans[i][cntd[j]] = min(ans[i][cntd[j]], sum);
    }
  }
  map<vector<int>, int> id;
  for (int i = 0; i < a.size(); i++) {
    id[a[i]] = i;
    for (int j = 0; j < a.size(); j++) {
      int sol = 1e9;
      for (int y = 1; y <= 1000; y++) {
        sol = min(sol, ans[i][y] + ans[j][y]);
      }
      best[i][j] = sol;
    }
  }
  for (int i = 2; i < N; i++) p[i] = 1;
  for (int i = 2; i < N; i++) {
    if (p[i]) {
      for (int j = i; j < N; j += i) {
        if (j > i) p[j] = 0;
        int aux = j, g = 0;
        while (aux % i == 0) {
          aux /= i;
          g++;
        }
        gr[j].push_back(g);
      }
    }
  }
  for (int i = 1; i < N; i++) {
    sort(gr[i].rbegin(), gr[i].rend());
    rofl[i] = id[gr[i]];
  }
  int q;
  cin >> q;
  while (q--) {
    int a, b;
    cin >> a >> b;
    cout << best[rofl[a]][rofl[b]] << "\n";
  }
  return 0;
}
