#include <iostream>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int t, a, b, maxd, count;

    cin >> t;
    while(t--){
        cin >> a >> b;
        count = 0;
        while(a!=0 && b!=0){
            maxd = max(a, b);
            if(maxd == a){
                a = abs(a-b);
            }else{
                b = abs(a-b);
            }
            count++;
        }

        cout << count << endl;
    }
	
	return 0;
}