#include <iostream>
using namespace std;
int main()
{
    int n,m,testCases;
    cin>>testCases;
    while (testCases--) {
        cin>>n>>m;
        int cnt = 0;
        if (n == m) {
            cnt = 1;
            cout<<cnt<<endl;
            continue;
        }
        while (n!=1&&m!=1&&n&&m) {
            if (n > m) {
                cnt += n/m;
                n = n%m;
            }
            else if (n < m) {
                cnt += m/n;
                m = m%n;
            }
        }
        cnt += n*m;
        cout<<cnt<<endl;
    }
}