C++ :

#include <iostream>
#include "bit"
#include "vector"
#include "unordered_set"
#include "unordered_map"
#include "set"
#include "queue"
#include "algorithm"
#include "bitset"
#include "cstring"
#include "cmath"

using namespace std;

int n, x, y;

int main() {
    cin >> n;
    while (n--) {
        cin >> x >> y;
        int c = 0;
        while (true) {
            if (x == y) {
                cout << c << endl;
                break;
            }
            if (x < y) swap(x, y);

            int i = 2;
            for (; i * i <= x; i++) {
                if (x % i == 0) {
                    break;
                }
            }
            if (i * i > x) {
                x = 1;
            } else {
                x /= i;
            }
            c++;
        }
    }
}