#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
using namespace std;

typedef long long LL;

LL read(){
    char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    LL x,tag;
    if(ch=='-') x=0,tag=-1;
    else x=ch-'0',tag=1;
    ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*tag;
}

void writeln(LL x){
    if(!x) putchar('0');
    else{
        if(x<0) putchar('-'),x=abs(x);
        LL ch[50],l=0;
        while(x) ch[l++]=x%10,x/=10;
        while(l) putchar(ch[--l]+'0');
    }
    putchar('\n');
}

LL solve(int a,int b){
    if(!a||!b) return 0;
    if(a<b) swap(a,b);
    return a/b+solve(a%b,b);
}

void work(){
    int n,m;
    n=read();
    m=read();
    writeln(solve(n,m));
}

int main(){
    int kase=read();
    while(kase--) work();
    return 0;
}