#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){
            if (a >= b){
                a = abs(a-b);
                //printf("%d\n", a);
                count++;
            }
            else{
                b = abs(b-a);
                //printf("%d\n", b);
                count++;
                
            }
        }

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

    return 0;
}