#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", print_args(__VA_ARGS__)
template <class... T>
void print_args(T... args) { ((cerr << args << ' '), ...) << '\n'; }
typedef long long ll;
const int mod = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const int N = 2E5 + 10;
//a%x=0,b%x=0->(a-b)%x=0
//前两种操作a-b不变
//a-b的质因子固定不变
//第三种操作其实就是不断/因子x的过程
//最优结果肯定是先调整ab使%x=0，然后/x
//1e9的数的质因子>sqrt(n)的最多一个，可以暴力找
int prime[N], vis[N], idx;
map<pii, int> dp;//记忆化
vector<int> g;
int a, b;
void ini() {
    for (int i = 2; i < N; i++) {
        if (!vis[i]) prime[idx++] = i;
        for (int j = 0; j < idx && prime[j] * i < N; j++) {
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}
void get_prime(int x) {
    int res = x;
    for (int i = 0; i < idx; i++) {
        int y = prime[i];
        if (y > res) break;
        if (x % y == 0) g.push_back(y);
        while (x % y == 0) {
            x /= y;
        }
    }
    if (x > 1) g.push_back(x);
}
int dfs(int a, int d) {//复杂度d*2,a受d牵连,状态只有两个
    if (a == 1) return 0;
    if (d == 1) return a - 1;//互质，只能一个一个减
    if (dp[{a, d}] != 0) return dp[{a, d}];
    for (auto x : g) {
        if (x > d) break;
        if (d % x) continue;
        int mn = min(dfs(a / x + 1, d / x) + x - a % x, dfs(a / x, d / x) + a % x);
        if (dp[{a, d}] == 0) dp[{a, d}] = mn + 1;
        else dp[{a, d}] = min(dp[{a, d}], mn + 1);
    }
    return dp[{a, d}];
}
void _() {
    if (a > b) swap(a, b);
    get_prime(b - a);
    cout << dfs(a, b - a) << '\n';//b = a + (b - a)
}
void input() {
    cin >> a >> b;
    g.clear();
    dp.clear();
}
void sol();
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    ini();

    int _ = 1;
    cin >> _;
    while (_--) {
        sol();
    }
    return 0;
}
void sol() {
    input(); _();
}