#include #include #include #include #include #include // for gcd #include using namespace std; // キャッシュ機能を実現するためのunordered_mapを使用 unordered_map> divisor_cache; // 整数Nのすべての約数を求める関数 vector Divisors(long long N) { if (divisor_cache.count(N)) return divisor_cache[N]; vector divisors; for (long long i = 1; i * i <= N; ++i) { if (N % i == 0) { divisors.push_back(i); if (i != N / i) divisors.push_back(N / i); } } sort(divisors.begin(), divisors.end()); return divisor_cache[N] = divisors; } // 木構造を構築する関数 vector> tree(long long p, long long q) { vector> retu; vector D = Divisors(q - p); const long long M = 1e18; while (q - p >= 2) { long long mi = M; for (size_t i = 1; i < D.size(); ++i) { if ((q - p) % D[i] == 0) { mi = min(mi, (-p) % D[i] + D[i]); // 値の正規化 } } long long pp = p + mi; long long qq = q + mi; long long g = gcd(pp, qq); retu.emplace_back(q - p, p, pp); p = pp / g; q = qq / g; } retu.emplace_back(1, p, M); return retu; } int main() { int Q; cin >> Q; while (Q--) { long long a, b, c, d; cin >> a >> b >> c >> d; auto tree0 = tree(a, b); auto tree1 = tree(c, d); assert(tree0.size() <= 30); assert(tree1.size() <= 30); sort(tree0.begin(), tree0.end()); sort(tree1.begin(), tree1.end()); long long D = 0, A = 0; while (!tree0.empty() && !tree1.empty()) { if (get<0>(tree0.back()) < get<0>(tree1.back())) { tree1.pop_back(); } else if (get<0>(tree0.back()) > get<0>(tree1.back())) { tree0.pop_back(); } else { auto [d0, a0, b0] = tree0.back(); auto [d1, a1, b1] = tree1.back(); tree0.pop_back(); tree1.pop_back(); long long a = max(a0, a1); long long b = min(b0, b1); if (a <= b) { D = d0; A = a; break; } } } cout << A << " " << A + D << endl; } return 0; }