#include<iostream>
using namespace std;
int MAX(int a, int b){
    return a > b ? a : b;
}
int MIN(int a, int b){
    return a < b ? a : b;
}
int main(){
    int T, i, j, m, n,a,b,total;
    cin >> T;
    while (T--){
        cin >> n >> m;
        total = 0;
        a = MAX(m, n);
        b = MIN(m, n);
        while (a%b != 0){
            total += a / b;
            m = a%b;
            a = b;
            b = m;
        }
        total += a / b;
        cout << total << endl;
    }
    return 0;
}