#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
const int mod=1000000007;
const int N=111111;
using namespace std;
int main(){
        int T,n,m,i,j;
        int sum;
        cin>>T;
        while(T--){
                cin>>n>>m;
                sum=0;
                if(n==m){
                        cout<<1<<endl;
                        continue;
                }
                while(n!=1&&m!=1&&m!=n){
                        if(n<m)
                                m-=n;
                        else n-=m;
                        sum++;
                }
                if(n==1||m==1){
                        if(n==1)sum+=m;
                        else sum+=n;
                }else sum++;
                cout<<sum<<endl;
        }return 0;
}