#include <iostream>

using namespace std;

void calculate(int p, int q);

int n;
int p[1000], q[1000];

int main() {

    //cout<<"Starting..."<<endl;

    cin>>n;

    for( int i=0; i<n; i++) {
        cin>>p[i];
        cin>>q[i];
    }

    for( int i=0; i<n; i++) {
        calculate(p[i], q[i]);
    }

    //system("pause");
    return 0;
}

void calculate(int p, int q) {


    /*if(p!=1) {*/
        int a=p;
        p=q;
        q=a;

        int w = p/q;
        cout << w << " ";
        p = p - (q*w);
        /*if(q>1)*/ calculate(p, q);

    /* } else {
        cout << q << endl;
    }*/
}