#include<algorithm>
#include<cstring>
#include<cstdio>
#define inf 1000000007
using namespace std;
int a,b,ans;
void gcd(int a,int b){
    if(b==0)return;
    ans+=(a/b);
    gcd(b,a%b);
}
int main(){
    //freopen("a.in","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&a,&b);ans=0;if(a<b)swap(a,b);gcd(a,b);
        printf("%d\n",ans);
    }
    return 0;
}