#include<cstdio>
#include<iostream>
#include<cstring>
#include<set>
#include<map>
#include<vector>
#include<cmath>
using namespace std;
int main(){
    int n,m;
    int t;
    cin>>t;
    while(t--){
            cin>>n>>m;
            int ans=0;
            while(1){
                if(n==m){
                        ans+=1;
                        break;
                }
                else if(n>m){
                        if(n%m==0) {
                                ans+=n/m;
                                break;
                        }
                        else{
                                ans+=n/m;
                                n=n%m;
                        }
                }
                else{
                        if(m%n==0) {
                                ans+=m/n;
                                break;
                        }
                        else{
                                ans+=m/n;
                                m=m%n;
                        }
                }

            }
            cout<<ans<<endl;
    }
    return 0;
}