// Kattis Contest Problem: A Rational Sequence 2
#include <iostream>
#include <fstream>
using namespace std;

int ftn(int p, int q);

int main() {
    int k, P, p, q;
    char c;
    fstream ifs("sample001.in", fstream::in);
    fstream ofs("check.ans", fstream::out);
    ifs >> P;

    while (P--) {
        ifs >> k >> p >> c >> q;
        ofs << k << " " << ftn(p, q);
    }
    cin.ignore();
    cin.get();
    return 0;
}

int ftn(int p, int q) {
    //base case
    if (p == 1 && q == 1) return 1;
    if (p > q) {
        return 1 + 2 * ftn(p - q, q);
    }
    else {
        return 2 * ftn(p, q - p);
    }
}