cf 267A

#include<stdio.h>

int main()
{
    int n, i;
    scanf("%d", &n);

    long long a[n], b[n];
    for(i = 0; i < n; i++) scanf("%lld %lld", &a[i], &b[i]);

    for(i = 0; i < n; i++)
    {
        long long cnt = 0;
        while(a[i] != 0 && b[i] != 0)
        {
            if(a[i] < b[i])
            {
                cnt += b[i] / a[i];
                b[i] %= a[i];
            }
            //printf("1 a %lld b %lld %lld\n", a[i], b[i], cnt);
            //if(a[i] == 0 || b[i] == 0) break;
            else
            {
                cnt += a[i] / b[i];
                a[i] %= b[i];
            }
            //printf("2 a %lld b %lld %lld\n", a[i], b[i], cnt);
            if(a[i] == 0 || b[i] == 0) break;
        }
        if(a[i] == 0 || b[i] == 0) printf("%lld\n", cnt);
    }
}