#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
const int inf = 1000000000;
const int maxn = 1000005;
const int maxa = 300005;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  if (b < 0) return -1;
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
int INF = 10000000;
clock_t start, finish;
const int N = 1000005;
const int M = 1005;
int mn[maxn], pri[maxn], equ[maxn];
int F(int x, vector<int> &v) {
  v.clear();
  while (x != 1) {
    int p = mn[x];
    int cnt = 0;
    for (; x % p == 0; x /= p, cnt++)
      ;
    v.push_back(cnt);
  }
  sort(v.begin(), v.end(), [](int a, int b) { return a > b; });
  vector<int> V = v;
  int ans = 1;
  for (int i = 0; i < v.size(); i++)
    for (; V[i]--; ans *= pri[i + 1])
      ;
  return ans;
}
int cnt;
int id[maxn];
int dis[300][1005];
int f[1005], g[1005];
void work(int *ans, vector<int> &v) {
  for (; v.size() < 25; v.push_back(0))
    ;
  memset(f, 10, sizeof(f));
  f[1] = 0;
  for (auto i : v) {
    memset(g, 10, sizeof(g));
    for (int j = 0; j <= 24; j++)
      for (int k = 1000 / (j + 1); k >= 1; k--)
        g[k * (j + 1)] = min(g[k * (j + 1)], f[k] + abs(i - j));
    swap(f, g);
  }
  for (int i = 1; i <= 1000; i++) ans[i] = f[i];
}
int main() {
  for (int i = 2; i < maxn; i++) {
    if (!mn[i]) {
      mn[i] = i;
      pri[++*pri] = i;
      for (int j = 2; j <= (maxn - 1) / i; j++)
        if (!mn[i * j]) mn[i * j] = i;
    }
  }
  vector<int> v;
  for (int i = 1; i < maxn; i++) {
    equ[i] = F(i, v);
    if (equ[i] == i) {
      id[i] = ++cnt;
      work(dis[cnt], v);
    }
  }
  int Q;
  scanf("%d", &Q);
  while (Q--) {
    int x, y, ans = (1ll << 30);
    scanf("%d%d", &x, &y);
    x = id[equ[x]];
    y = id[equ[y]];
    for (int i = (int)(1); i <= (int)(1000); i++)
      ans = min(ans, dis[x][i] + dis[y][i]);
    printf("%d\n", ans);
  }
}
