#include <iostream>
#include <cmath>
using namespace std;
int main() {
    
    //SAYED AL MAMUN_LU
    
    int t;
    cin >> t;

    while (t--) {
        long long int a, b;
        int sum = 0;
        cin >> a >> b;

        while (a > 0 && b > 0) {
            if (a > b) {
                a = abs(a - b);
            } 
            else {
                b = abs(b - a);
            }
            sum++;
        }

        cout << sum << endl;
    }

    return 0;
}