#include<bits/stdc++.h>

#define int long long

int solve(int a,int b){
    if(a==0 && b==0)return 0;
    if(a==0||b==0)return 1;
    int g = std::gcd(a,b);
    int k1 = a / g, k2 = b / g; 
    if(k1==1){
        return solve(0,b-g)+1;
    }
    if(k1%2){
        return solve(a-g,b)+1;
    }
    return solve(a,b-g)+1;
}

void solve(){
    int a,b;
    std::cin >> a >> b; 

    std::cout<<solve(a,b)<<"\n";


}
 
signed main(){
    
    int t = 1;
    std::cin >> t;
    while(t--)solve();

    return 0;
}

answer.code: In function ‘long long int solve(long long int, long long int)’:
answer.code:8:18: error: ‘gcd’ is not a member of ‘std’
    8 |     int g = std::gcd(a,b);
      |                  ^~~