#include<iostream>
using namespace std;
long long gcd(long long x,long long y){
    if(x*y==0)return x+y;
    if(x>y)swap(x,y);
    if(y%x==0)return x;
    return gcd(x,y%x);
}
int main(){
    int t;cin>>t;while(t--){
        long long x,y;
        cin>>x>>y;
        // cout<<gcd(x,y)<<endl;
        if(x>y)swap(x,y);
        int cnt=0;
        while(x!=0&&y!=0){
            long long G=gcd(x,y);
            x/=G;
            y/=G;
            if(gcd(x-1,y)>gcd(x,y-1)){
                x--;
            }else{
                y--;
            }
            cnt++;
        }
        if(x+y)
            cout<<cnt+1<<endl;
        else 
            cout<<cnt<<endl;
    }
    return 0;
}