#include <stdio.h>

int main() {
    unsigned long long int a, b;
    int n;
    scanf("%d",&n);
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &a, &b);
        unsigned long long int count = 0;
        while (b != 0) {
            unsigned long long int x = b;
            b = a % b;
            a = x;
            count++;
        }
        printf("%lld\n", count);
    }
    return 0;
}