#include <bits/stdc++.h>   using namespace std;   const int N = 1000000;   int T, tot, prod, mn[1000010];   bool solved[10000][11];   bitset<1000> b[10000][11];   vector<int> V, prime;   unordered_map<int, int> id;   int main() {     scanf( %d , &T);     for (int i = 2; i <= N; i++)       if (!mn[i]) {         if (prime.size() < 1000) prime.push_back(i);         for (int j = i; j <= N; j += i) mn[j] = i;       }     auto get = [&](long long x) {       V.clear();       int lst = 50;       while (x > 1) {         int c = 0, t = x <= N ? mn[x] : 0;         if (!t) {           for (int i = lst; ~i; i--) {             if (!(x % prime[i])) {               t = prime[i], lst = i;               break;             }           }         }         while (!(x % t)) x /= t, c++;         V.push_back(c);       }       sort(V.begin(), V.end(), greater<int>());       int z = prod = 1;       for (int i = 0; i < V.size(); i++) {         prod *= V[i] + 1;         for (int j = 0; j < V[i]; j++) z *= prime[i];       }       return z;     };     for (int i = 1; i <= N; i++) {       if (i == get(i)) id[i] = ++tot;     }     function<void(int, int)> solve = [&](int x, int step) {       int y = get(x);       if (prod >= 1000) return;       if (!id.count(x)) id[x] = ++tot;       int $ = id[x];       if (solved[$][step]) return;       solved[$][step] = 1;       if (!step) {         b[$][step][prod] = 1;         return;       }       vector<int> V2 = V;       for (int i = 0; i < V2.size(); i++) {         int v = get(x / prime[i]);         solve(v, step - 1), b[$][step] |= b[id[v]][step - 1];         v = get(1LL * x * prime[i]);         if (v <= N * 100) solve(v, step - 1), b[$][step] |= b[id[v]][step - 1];       }       int v = get(1LL * x * prime[V2.size()]);       if (v <= N * 100) solve(v, step - 1), b[$][step] |= b[id[v]][step - 1];     };     for (int i = 1; i <= N; i++)       if (id[i]) {         for (int j = 0; j <= 10; j++) solve(i, j);       }     while (T--) {       int x, y, ans = INT_MAX;       scanf( %d %d , &x, &y);       x = get(x), y = get(y);       for (int i = 0; i <= 10; i++) {         for (int j = 0; j <= 10; j++)           if (i + j < ans) {             if ((b[id[x]][i] & b[id[y]][j]).any()) ans = min(ans, i + j);           }       }       assert(ans <= 10);       printf( %d n , ans);     }     return 0;   }   