#include <bits/stdc++.h>
using namespace std;
int t;
int ai, bi;
vector<long long> v;
long long primes[8] = {2, 3, 5, 7, 11, 13, 17, 19};
void f(multiset<int> s, int sum, int product) {
  if (sum >= 23 || product > 300) {
    return;
  }
  long long prod = 1;
  int cnt = 0;
  for (multiset<int>::iterator it = s.begin(); it != s.end(); ++it) {
    prod *= pow(primes[s.size() - 1 - cnt], *it);
    cnt++;
  }
  v.push_back(prod);
  int m = *s.begin();
  for (int i = 1; i <= m; i++) {
    s.insert(i);
    f(s, sum + i, product * (i + 1));
    s.erase(i);
  }
}
vector<int> expt;
long long convert(int n) {
  int idx = 2;
  int g = n;
  while (g != 1) {
    if (idx * idx > n) {
      expt.push_back(1);
      break;
    } else {
      int cnt = 0;
      while (g % idx == 0) {
        cnt++;
        g /= idx;
      }
      if (cnt > 0) {
        expt.push_back(cnt);
      }
      idx++;
    }
  }
  sort(expt.begin(), expt.end());
  int toreturn = 1;
  for (int i = 0; i < expt.size(); i++) {
    toreturn *= pow(primes[expt.size() - 1 - i], expt[i]);
  }
  expt.clear();
  return toreturn;
}
map<int, int> M;
int dist[700][700];
int V;
int adj[700][700];
const int inf = pow(10, 9);
void floydWarshall() {
  for (int i = 0; i < V; i++) {
    for (int j = 0; j < V; j++) {
      dist[i][j] = adj[i][j];
    }
  }
  for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
      for (int j = 0; j < V; j++) {
        if (dist[i][k] + dist[k][j] < dist[i][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      }
    }
  }
}
int bestdiv[300][300];
int main() {
  multiset<int> s;
  v.push_back(1);
  for (int i = 1; i <= 22; i++) {
    s.insert(i);
    f(s, i, i);
    s.erase(i);
  }
  sort(v.begin(), v.end());
  V = v.size();
  for (int i = 0; i < v.size(); i++) {
    M[v[i]] = i;
    for (int j = i + 1; j < v.size(); j++) {
      int a = v[i];
      int b = v[j];
      int cnt = 0;
      for (int k = 0; k < 8; k++) {
        int cnti = 0;
        while (a % primes[k] == 0) {
          cnti++;
          a /= primes[k];
        }
        int cntj = 0;
        while (b % primes[k] == 0) {
          cntj++;
          b /= primes[k];
        }
        cnt += abs(cnti - cntj);
      }
      if (cnt == 1) {
        adj[i][j] = 1;
        adj[j][i] = 1;
      } else {
        adj[i][j] = inf;
        adj[j][i] = inf;
      }
    }
  }
  floydWarshall();
  for (int i = 0; i < v.size(); i++) {
    if (v[i] > 1000000) break;
    for (int j = 1; j < 300; j++) {
      bestdiv[i][j] = inf;
    }
    for (int j = 0; j < v.size(); j++) {
      int g = v[j];
      int prod = 1;
      for (int k = 0; k < 8; k++) {
        int cnt = 0;
        while (g % primes[k] == 0) {
          cnt++;
          g /= primes[k];
        }
        prod *= (cnt + 1);
      }
      bestdiv[i][prod] = min(bestdiv[i][prod], dist[i][j]);
    }
  }
  scanf("%d", &t);
  for (int i = 0; i < t; i++) {
    scanf("%d %d", &ai, &bi);
    ai = M[convert(ai)];
    bi = M[convert(bi)];
    int ans = inf;
    for (int j = 1; j < 300; j++) {
      ans = min(ans, bestdiv[ai][j] + bestdiv[bi][j]);
    }
    printf("%d\n", ans);
  }
}
