#include<iostream>
#include<cstring>
#include<vector>
#include<numeric>
using namespace std;
using LL = long long;
const int maxn = 5005;
int f[maxn][maxn];
pair<int, int> pre[maxn][maxn];
LL a, b;

int dp(int x, int y){
    if (y > a) return 1e9;
    if (x == 0 and b - y == 0) return 0;
    if (x == 0 or b - y == 0) return 1;
    if (~f[x][y]) return f[x][y];
    int ans = 1e9;
    LL t = gcd(x, b - y);
    ans = min(ans, 1 + dp(x - t, y));
    ans = min(ans, 1 + dp(x, y + t));
    return f[x][y] = ans;
}

int main(){

#ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while(T--){
        cin >> a >> b;
        for(int i = 0; i <= a; i++){
            for(int j = 0; j <= a; j++){
                f[i][j] = -1;
            }
        }
        cout << dp(a, 0) << '\n';
    }

}