#include <bits/stdc++.h>
using namespace std;
const int INF = numeric_limits<int>::max() / 2;
const int MAX_NODES = 300;
const int MAX_NUM_DIV = 300;
const int MAX_N = 1000001;
int divisors[MAX_NUM_DIV][MAX_NUM_DIV];
int num_divisors[MAX_NUM_DIV];
int last_node;
int tree[MAX_NODES][MAX_NUM_DIV];
int dp[MAX_NODES][MAX_NUM_DIV];
int table[MAX_NODES][MAX_NODES];
int num2code[MAX_N];
const int SIEVEN = MAX_N;
int lp[SIEVEN + 1];
int ps[SIEVEN];
int nps;
void sieve() {
  memset(lp, 0, sizeof(lp));
  nps = 0;
  for (int i = 2; i <= SIEVEN; i++) {
    if (not lp[i]) lp[i] = ps[nps++] = i;
    for (int j = 0; j < nps and ps[j] <= lp[i] and i * ps[j] <= SIEVEN; j++)
      lp[i * ps[j]] = ps[j];
  }
}
void encode(vector<int>& code, int n) {
  code.clear();
  while (n > 1) {
    int p = lp[n];
    int e = 0;
    while (n % p == 0) {
      n /= p;
      e++;
    }
    code.push_back(e);
  }
  sort(code.begin(), code.end());
}
int insert(const vector<int>& code) {
  int r = 1;
  for (int k = 0; k < code.size(); k++) {
    if (not tree[r][code[k]]) {
      tree[r][code[k]] = ++last_node;
    }
    r = tree[r][code[k]];
  }
  return r;
}
void fillTree() {
  vector<int> code;
  for (int n = 1; n < MAX_N; n++) {
    encode(code, n);
    num2code[n] = insert(code);
  }
}
void precomputeDivisors() {
  for (int d = 2; d < MAX_NUM_DIV; d++) {
    for (int k = d; k < MAX_NUM_DIV; k += d) {
      divisors[k][num_divisors[k]++] = d;
    }
  }
}
void doDp(int r, int p, int v) {
  dp[r][1] = v + dp[p][1];
  for (int k = 2; k < MAX_NUM_DIV; k++) {
    dp[r][k] = INF;
    for (int i = 0; i < num_divisors[k]; i++) {
      int d = divisors[k][i];
      dp[r][k] = min(dp[r][k], dp[p][k / d] + abs(d - 1 - v));
    }
  }
  for (int k = 1; k < MAX_NUM_DIV; k++) {
    if (tree[r][k]) {
      doDp(tree[r][k], r, k);
    }
  }
}
void precomputeTable() {
  for (int a = 1; a < MAX_NODES; a++) {
    for (int b = a + 1; b < MAX_NODES; b++) {
      table[a][b] = INF;
      for (int k = 1; k < MAX_NUM_DIV; k++) {
        table[a][b] = min(table[a][b], dp[a][k] + dp[b][k]);
      }
      table[b][a] = table[a][b];
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  ++last_node;
  sieve();
  precomputeDivisors();
  fillTree();
  doDp(1, 1, 0);
  precomputeTable();
  int ntc;
  cin >> ntc;
  for (int tc = 0; tc < ntc; tc++) {
    int a, b;
    cin >> a >> b;
    a = num2code[a];
    b = num2code[b];
    if (a > b) swap(a, b);
    cout << table[a][b] << '\n';
  }
}
