#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

const int N = 55;
int a, b;
vector<int> v[N];

void factor(int n) {
    v[1].clear();
    int lim = sqrt(n);
    for (int i = 2; i <= lim; i++) {
        if (!(n % i)) {
            v[1].push_back(i);
            while (!(n % i)) n /= i;
        }
    }
    if (n != 1) v[1].push_back(n);
}

int calc(int dep, int a, int b) {
    if (a == 1) return 0;
    int d = b - a, res = a - 1;
    if (res == 1) return res;
    v[dep + 1].clear();
    for (int p : v[dep]) {
        if (!(d % p)) {
            v[dep + 1].push_back(p);
        }
    }
    for (int p : v[dep + 1]) {
        if (!(a % p)) {
            res = min(res, 1 + calc(dep + 1, a / p, b / p));
        } else {
            if (a > p) {
                int t = a - a / p * p;
                if (t + 1 < res) res = min(res, t + 1 + calc(dep + 1, (a - t) / p, (b - t) / p));
            }
            int t = (a / p + 1) * p - a;
            if (t + 1 < res) res = min(res, t + 1 + calc(dep + 1, (a + t) / p, (b + t) / p));
        }
    }
    return res;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &a, &b);
        if (a > b) swap(a, b);
        if (a == 1) printf("0\n");
        else if (a == b) printf("1\n");
        else {
            factor(b - a);
            printf("%d\n", calc(1, a, b));
        }
    }
    return 0;
}