#include <stdio.h>

int main(){

    int a, b, t;

    scanf("%d", &t);

    int i = 1;

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

        int count = 0;

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

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

    return 0;
}