#pragma optimize GCC("Ofast")
#include <bits/stdc++.h>

using i64 = long long;
constexpr int fk_max = 1e9;


__int128 gcd(__int128 a, __int128 b) {
    return b == 0 ? a : gcd(b, a % b);
}

std::array<i64, 3> exgcd(i64 a, i64 b) {
    if (b == 0) {
        return {a, 1, 0};
    }
    auto [g, x, y] = exgcd(b, a % b);
    return {g, y, x - a / b * y};
}

i64 inline floor(i64 a, i64 b) {
    return a / b - ((a ^ b) < 0 && a % b);
}
i64 inline ceil(i64 a, i64 b) {
    return -floor(-a, b);
}

std::array<i64, 2> inline valid(i64 a, i64 b, i64 c, i64 d, i64 x, i64 y) {
    // auto [d, x, y] = exgcd(a, b);
    if (c % d) return {0, -1};
    x *= c / d;
    y *= c / d;
    i64 dx = b / d;
    i64 dy = -a / d;
    // std::cerr << a << " " << b << " " << c << " " << x << " " << y << " " << "\n";
    i64 k = dx > 0 ? ceil(-x, dx) : floor(-x, dx);
    x += k * dx, y += k * dy;

    // std::cerr << a << " " << b << " " << c << " " << x << " " << y << " " << "\n";
    return {y >= 0, x};

}
using namespace std;
map<pair<int,int>,pair<int,int>> ans;
void solve(){
    i64 a, b;
    std::cin >> a >> b;
    if (ans.count({a, b})) {
        auto [c,d] = ans[{a,b}];
        cout<< c<< ' '<<d<< '\n';
        return;
    }
    i64 remb = b;
    while(remb % 2 == 0){
        remb /= 2;
    }
    while(remb % 5 == 0) {
        remb /= 5;
    }

    std::vector<i64> zy;
    for (int i = 1; 1ll * i * i <= remb; ++i) {
        if (remb % i == 0) {
            zy.push_back(i);
        }
        if (1ll * i * i == remb) continue;

        zy.push_back(remb / i);
    }
    std::sort(std::begin(zy), std::end(zy));

    i64 c = 1e18, d = 1e18;

    __int128 cx_a = a;
    if (cx_a % remb == 0) {
        std::cout << "0 1\n";
        return;
    }

    // ad + bc + xbd = 0
    // for (auto zz : zy) {
        auto [g, x, y] = exgcd(b, -remb);
        // i64 cnt = 0;
        for(i64 i = 1; i <= fk_max; i = i * 2) {
            for (i64 j = i; j <= fk_max; j *= 5) {
                // cnt++;
                // continue;
                i64 dd = j ;
                if (dd > fk_max) break;
                auto [ok, cc] = valid(b, - remb , - a * dd, g, x, y);
                if (!ok) continue;
                // std::cerr << ": " << dd  << "\n";
                // i64 gg = std::gcd(cc, dd);
                // cc /= gg;
                // dd /= gg;
                if (cc < c) {
                    c = cc;
                    d = dd;
                    if (c == 1) break;
                } else if (cc == c) {
                    d = std::min(dd, d);
                }
            }
        }
        // std::cout<< cnt<< '\n';
        // break;
    // }
    std::cout << c << " ";
    std::cout << d;
    std::cout <<  "\n";
    ans[{a,b}] = {c,d};
}

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);

    int t;
    std::cin >> t;
    while(t--){
        solve();
    }

    return 0;
}