#include <bits/stdc++.h>
using namespace std;
template <class TH>
void _dbg(const char *sdbg, TH h) {
  cerr << sdbg << " = " << h << endl;
}
template <class TH, class... TA>
void _dbg(const char *sdbg, TH h, TA... a) {
  while (*sdbg != ',') cerr << *sdbg++;
  cerr << " = " << h << ", ";
  _dbg(sdbg + 1, a...);
}
const int maxn = (1e6) + 7;
const int maxk = 20;
const int inf = (1e9) + 7;
const long long LLinf = ((long long)1e18) + 7LL;
const long double eps = 1e-9;
const long long mod = 1e9 + 7;
vector<int> V;
int suma;
int ilo = 1;
int num = 0;
map<vector<int>, int> mapa, il;
set<int> zb;
map<int, int> nu;
set<vector<int> > dwa;
vector<int> wek[maxn];
int dziel[maxn];
int odl[100005];
vector<int> graf[maxn], wektor[maxn];
int ilocz[maxn];
int numer = 0;
void generuj(int x) {
  if (!mapa.count(V)) {
    mapa[V] = num;
    wektor[num] = V;
    il[V] = ilo;
    zb.insert(ilo);
    ilocz[num] = ilo;
    num++;
  }
  for (int i = x;; i++) {
    if (suma + i > 22) break;
    suma += i;
    ilo *= i + 1;
    V.push_back(i);
    generuj(i);
    V.pop_back();
    suma -= i;
    ilo /= i + 1;
  }
}
int kto(vector<int> V) {
  sort(V.begin(), V.end());
  if (mapa.count(V)) return mapa[V];
  return -1;
}
void ae(int a, int b) {
  graf[a].push_back(b);
  graf[b].push_back(a);
}
bool vis[maxn];
int wyn[5005][1000];
int wynik[5000][5000];
void bfs(int x) {
  for (int i = 0; i < max(numer, num); i++) odl[i] = inf;
  queue<int> q;
  q.push(x);
  odl[x] = 0;
  while (q.size() != 0) {
    int a = q.front();
    wyn[x][ilocz[a]] = min(wyn[x][ilocz[a]], odl[a]);
    q.pop();
    for (auto s : graf[a]) {
      if (odl[s] > odl[a] + 1) {
        odl[s] = odl[a] + 1;
        q.push(s);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  generuj(1);
  for (int i = 0; i < 5000; i++)
    for (int j = 0; j < 1000; j++) wyn[i][j] = inf;
  for (auto s : zb) {
    nu[s] = numer++;
  }
  for (auto &s : il) s.second = nu[s.second];
  for (int i = 0; i < num; i++) ilocz[i] = nu[ilocz[i]];
  wek[1] = {};
  dwa.insert({});
  for (int i = 2; i < maxn; i++) {
    if (dziel[i] == 0)
      for (int j = i; j < maxn; j += i) dziel[j] = i;
    int xd = i;
    int licz = 0;
    while (xd % dziel[i] == 0) {
      xd /= dziel[i];
      licz++;
    }
    wek[i] = wek[xd];
    wek[i].push_back(licz);
    sort(wek[i].begin(), wek[i].end());
    dwa.insert(wek[i]);
  }
  for (auto s : mapa) {
    auto xd = s.first;
    for (auto &v : xd) {
      v++;
      int g = kto(xd);
      if (g != -1) ae(s.second, g);
      v--;
    }
    xd.push_back(1);
    int g = kto(xd);
    if (g != -1) ae(s.second, g);
  }
  for (auto s : dwa) bfs(mapa[s]);
  bfs(0);
  for (auto s : dwa)
    for (auto v : dwa) {
      int a = mapa[s];
      int b = mapa[v];
      wynik[a][b] = inf;
      for (int k = 0; k < numer; k++) {
        wynik[a][b] = min(wynik[a][b], wyn[a][k] + wyn[b][k]);
      }
    }
  int a = 0;
  for (auto v : dwa) {
    int b = mapa[v];
    wynik[a][b] = inf;
    for (int k = 0; k < numer; k++) {
      wynik[a][b] = min(wynik[a][b], wyn[a][k] + wyn[b][k]);
    }
  }
  int q;
  cin >> q;
  while (q--) {
    int b;
    cin >> a >> b;
    a = mapa[wek[a]];
    b = mapa[wek[b]];
    if (a > b) swap(a, b);
    cout << wynik[a][b] << "\n";
  }
  return 0;
}
