#include <bits/stdc++.h>
using namespace std;
const int N = 1000001;
set<vector<int>> s;
vector<int> v[N];
int dp[289][31][1201], top[N];
vector<vector<int>> t;
int get(int x) {
  for (int i = 0; i < 289; i++)
    if (t[i] == v[x]) return i;
  throw;
}
int main() {
  ios::sync_with_stdio(false);
  for (int i = 1; i < N; i++) v[i] = vector<int>(7, 1);
  for (int i = 2; i < N; i++)
    if (!top[i])
      for (int j = 1; i * j < N; j++) {
        int cur = j, cc = 2;
        while (cur % i == 0) cur /= i, ++cc;
        v[i * j][top[i * j]] = cc;
        ++top[i * j];
      }
  for (int i = 1; i < N; i++) sort(v[i].begin(), v[i].end()), s.insert(v[i]);
  t = vector<vector<int>>(s.begin(), s.end());
  for (int i = 0; i < int(t.size()); i++)
    for (int j = 0; j <= 30; j++)
      for (int k = 0; k <= 1200; k++) dp[i][j][k] = 999;
  for (int i = 0; i < int(t.size()); i++) {
    vector<int> tmp;
    for (int j = 0; j < 7; j++) tmp.push_back(t[i][j]);
    dp[i][0][1] = 0;
    while (tmp.size() < 30) tmp.push_back(1);
    for (int j = 0; j < 30; ++j)
      for (int k = 1; k <= 1200; k++)
        if (dp[i][j][k] < 999)
          for (int l = max(1, tmp[j] - 30);
               k * l <= 1200 && l <= min(1200, tmp[j] + 30); ++l)
            dp[i][j + 1][k * l] =
                min(dp[i][j + 1][k * l], dp[i][j][k] + abs(tmp[j] - l));
  }
  int n;
  cin >> n;
  while (n--) {
    int t1, t2;
    cin >> t1 >> t2;
    int p1 = get(t1), p2 = get(t2), ans = 9000;
    for (int i = 1; i <= 1200; i++)
      ans = min(ans, dp[p1][30][i] + dp[p2][30][i]);
    cout << ans << endl;
  }
  return 0;
}
