#include <cstdio>
#include <iostream>
using namespace std;
int getint() {
    int r = 0; char c = getchar();
    for (; c < '0' || c > '9'; c = getchar());
    for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
    return r;
}
int T, n, m;
int main() {
    T = getint();
    while (T--) {
        int ans = 1;
        n = getint();
        m = getint();
        while (n != m) {
            if (n < m) swap(n, m);
            n -= m;
            ++ans;
        }
        printf("%d\n", ans);
    }
}