#include<stdio.h>
int main()
{
    int n;
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        if(b<a)
        {
            int t;
            t=a;
            a=b;
            b=t;
        }
        int ans=0;
        while(a!=0)
        {
            int t;
            ans+=b/a;
            t=a;
            a=b%a;
            b=t;
        }
        printf("%d\n",ans);
    }
    return 0;
}