#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using i128 = __int128;

vector<ll> p;
void init()
{
    for (ll i = 1; i <= 1e9; i *= 2) {
        for (ll j = 1; i * j <= 1e9; j *= 5) {
            p.push_back(i * j);
        }
    }
    sort(p.begin(), p.end());
}

ll get(ll x)
{
    while (x % 5 == 0) x /= 5;
    while (x % 2 == 0) x /= 2;
    return x;
}

i128 exgcd(i128 a, i128 b, i128& x, i128& y)
{
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    i128 gcd = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return gcd;
}

void solve()
{
    ll a, b, c;
    cin >> a >> b;
    if (count(p.begin(), p.end(), b) || a % b == 0) {
        cout << "0 1\n";
        return;
    }
    ll w = get(b);
    ll ans = LLONG_MAX, ansd;
    for (auto pp : p) {
        i128 d = pp * w;
        if (d > 1e9) break;
        for (i128 Y : p) {
            i128 x, y;
            i128 A = (i128)b * d, B = (i128)b * Y, C = (i128)a * d * Y;
            i128 t = exgcd(A, -B, x, y);
            if (t < 0) t = -t;
            if (C % t) continue;
            y *= C / t;
            if (y <= 0) {
                y += ((-y) / (A / t) + 1) * (A / t);
            }
            else {
                y -= (y / (A / t)) * (A / t);
                if (y <= 0) y += A / t;
            }

            assert(y > 0);
            if (y < ans) {
                ans = y;
                ansd = d;
            }
        }
    }
    cout << (ll)ans << " " << (ll)ansd << "\n";
}

int main()
{
    ios::sync_with_stdio(false), cin.tie(0);
    int tt;
    cin >> tt;
    init();
    while (tt--) {
        solve();
    }
    return 0;
}