#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long

int read()
{
    int x = 0; bool f = false; char c = getchar();
    while(c < '0' || c > '9') f |= (c == '-'), c = getchar();
    while(c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c & 15), c = getchar();
    return f ? -x : x;
}

int p[25], cnt[25], tot, K;
map< pair<int, int> , int> mp;
int dfs(int a, int K)
{
    if(mp.count(pair<int, int>(a, K)) == 1) return mp[pair<int, int>(a, K)];
    if(K == 1 || a == 1) return a - 1;
    int ans = 0x7fffffff;
    for(int i = 1; i <= tot; ++i)
    {
        if(cnt[i] > 0)
        {
            int temp = a % p[i];
            if(a == temp){ ans = min(ans, temp - 1); continue; }
            // if(temp > p[i] - temp)
            // {
                --cnt[i];
                ans = min(ans, p[i] - temp + 1 + dfs((a + p[i] - temp) / p[i], K / p[i]));
                // ++cnt[i];
            // }else if(temp < p[i] - temp)
            // {
                // --cnt[i];
                ans = min(ans, temp + 1 + dfs((a - temp) / p[i], K / p[i]));
                ++cnt[i];
            // }else if(temp == p[i] - temp)
            // {
            //     --cnt[i];
            //     ans = min(ans, temp + 1 + dfs((a - temp) / p[i], K / p[i]));
            //     ans = min(ans, temp + 1 + dfs((a + temp) / p[i], K / p[i]));
            //     ++cnt[i];
            // }
        }
    }
    return mp[pair<int, int>(a, K)] = ans;
}

void solve()
{
    int a = read(), b = read(), x = abs(a - b), y = x, yy = sqrt(y);
    while(tot) p[tot] = cnt[tot] = 0, --tot;
    K = 0;
    for(int i = 2; i <= yy; ++i)
    {
        if(y % i == 0)
        {
            ++tot, p[tot] = i;
            while(y % i == 0) ++cnt[tot], y /= i, ++K;
        }
    }
    if(y > 1) ++tot, p[tot] = y, cnt[tot] = 1, ++K;
    printf("%d\n", dfs(min(a, b), x));
}

int main()
{
    int T = read();
    while(T--) solve();
    return 0;
}