#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

const long long M=1LL<<60;

long long gcd(long long a,long long b){
    if(a>b){
        return gcd(b,a);
    }
    if(a==0){
        return b;
    }
    return gcd(b%a,a);
}
vector<long long> Divisors(long long N) {
    vector<long long> divisors;
    long long i;
    for (i = 1; i * i < N; ++i) {
        if (N % i == 0) {
            divisors.push_back(i);
        }
    }
    if (i * i == N) {
        divisors.push_back(i);
    }
    for (--i; i > 0; --i) {
        if (N % i == 0) {
            divisors.push_back(N / i);
        }
    }
    return divisors;
}

vector<tuple<long long, long long, long long>> f(long long p, long long q, const vector<long long>& D) {
    if (q - p == 1) {
        return { make_tuple(1, p, M) };
    }
    vector<tuple<long long, long long, long long>> lst;
    vector<long long> mods;
    for (size_t i = 1; i < D.size(); ++i) {
        long long d = D[i];
        if ((q - p) % d == 0) {
            mods.push_back((d+(-p) % d)%d);
        }
    }
    long long mi = *min_element(mods.begin(), mods.end());
    long long pp = p + mi;
    long long qq = q + mi;
    long long g = gcd(pp, qq);
    lst.push_back(make_tuple(q - p, p, pp));
    vector<tuple<long long, long long, long long>> sub_lst = f(pp / g, qq / g, D);
    lst.insert(lst.end(), sub_lst.begin(), sub_lst.end());
    return lst;
}

vector<tuple<long long, long long, long long>> tree(long long p, long long q) {
    vector<long long> D = Divisors(q - p);
    return f(p, q, D);
}

int main() {
    int Q;
    cin >> Q;
    for (int q = 0; q < Q; ++q) {
        long long a, b, c, d;
        cin >> a >> b >> c >> d;
        vector<tuple<long long, long long, long long>> tree0 = tree(a, b);
        vector<tuple<long long, long long, long long>> tree1 = tree(c, d);

        unordered_map<long long, vector<pair<long long, long long>>> dct;
        for (const auto& [d, a, b] : tree0) {
            dct[d].emplace_back(a, b);
        }
        for (const auto& [d, a, b] : tree1) {
            dct[d].emplace_back(a, b);
        }
    }

    return 0;
}