#include<cstdio>
using namespace std;
int main()
{
    int T,a,b,s;
    scanf("%d",&T);
    while(T--){
        s=0;
        scanf("%d%d",&a,&b);
        for(;;){
            if(a<b) a^=b^=a^=b;
            s+=a/b;
            a=a%b;
            if(a==0) break;
        }
        printf("%d\n",s);
    }
    return 0;
}