#include <iostream>

using namespace std;


int main()
{
    int T, m, n, x, y;
    cin >> T;
    while(T--) {
        cin >> x >> y;
        m = max(x, y);
        n = min(x, y);
        int sum = 1;
        while(m != n) {
            x = m - n;
            y = n;
            m = max(x, y);
            n = min(x, y);
            sum++;
        }
        cout << sum << endl;
    }
    return 0;
}