#include <bits/stdc++.h>
using namespace std;
const int oo = 0x3f3f3f3f;
const long long ooo = 9223372036854775807ll;
const int _cnt = 1000 * 1000 + 7;
const int _p = 1000 * 1000 * 1000 + 7;
const int N = 1000005;
const double PI = acos(-1.0);
const double eps = 1e-9;
int o(int x) { return x % _p; }
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
void file_put() {
  string s = "/home/jslijin/jslijin/code/";
  freopen((s + "code.in").c_str(), "r", stdin);
  freopen((s + "code.out").c_str(), "w", stdout);
}
const int _N = 300, _M = 900, max_step = 10, max_num = 1000000;
int dist[_N][_M], ans[_N][_M], f[N], id[N], X[N], Y[N];
vector<int> V[N];
int a, b, k, T, ret, cntx = 0, cnty = 0, prime[] = {2, 3, 5, 7, 11, 13, 17, 19};
bool cmp(int x, int y) { return x > y; }
void upd(int &x, int y) {
  if (y < x) x = y;
}
void dfs(int k, int step, int num, int div, int num_mx, int div_mx) {
  if (!X[num]) X[num] = ++cntx;
  if (!Y[div]) Y[div] = ++cnty;
  if (dist[X[num]][Y[div]] <= step) return;
  if (k >= 7) {
    upd(dist[X[num]][Y[div]], step);
    return;
  }
  for (int i = (0); i <= (num_mx); ++i) {
    if (num > max_num) return;
    for (int j = (0); j <= (div_mx); ++j)
      if (step + abs(i - j) <= max_step)
        dfs(k + 1, step + abs(i - j), num, div * (j + 1), i, j);
    num *= prime[k];
  }
}
int main() {
  scanf("%d", &T);
  memset(dist, oo, sizeof(dist)), memset(ans, -1, sizeof(ans)), id[1] = 1;
  for (int i = (1); i <= (N - 1); ++i) f[i] = i;
  for (int i = (2); i <= (N - 1); ++i) {
    if (f[i] > 1)
      for (int j = i; j <= N - 1; j += i) {
        k = 0;
        while (f[j] % i == 0) ++k, f[j] /= i;
        V[j].push_back(k);
      }
    sort((V[i]).begin(), (V[i]).end(), cmp), id[i] = 1;
    for (int j = (0); j <= ((int)V[i].size() - 1); ++j)
      for (int t = (1); t <= (V[i][j]); ++t) id[i] *= prime[j];
  }
  dfs(0, 0, 1, 1, 100, 100);
  while (T--) {
    scanf("%d%d", &a, &b);
    a = X[id[a]], b = X[id[b]];
    if (a > b) swap(a, b);
    if (ans[a][b] != -1) {
      printf("%d\n", ans[a][b]);
      continue;
    }
    ret = oo;
    for (int i = (1); i <= (cnty); ++i)
      ret = ((ret) < (dist[a][i] + dist[b][i]) ? (ret)
                                               : (dist[a][i] + dist[b][i]));
    ans[a][b] = ret, printf("%d\n", ret);
  }
  return 0;
}
