#include <stdio.h>

int main(){

    long long int a, b;
    int t;

    scanf("%d", &t);

    int i = 1;

    while(i <= t){
        scanf("%lld %lld", &a, &b);

        int count = 0;

        while(a != 0){
            a = abs(a);
            b = abs(b);
            if (a >= b){
                a = a-b;
                //printf("%d\n", a);
                count++;
            }
            else{
                b = b-a;
                //printf("%d\n", b);
                count++;
                if (b == 0){
                    break;
                }
            }
        }

        printf("%d\n", count);
        i++;
    }

    return 0;
}