#include<iostream>
#include<algorithm>
#include<cmath> 
using namespace std;
int n(int a,int b){
    if(a==b)
        return 1;
    if(a<b)
        swap(a,b);
    return 1+n(b,a-b); 
}
int main(void){
    int a,b;
    int T;
    cin>>T;
    while(T--){
        cin>>a>>b;
        cout<<n(a,b)<<endl;
    }
}