#include <bits/stdc++.h>

using namespace std;
#define int long long

const int mod = 998244353, mx = 1e9;

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int x1, y1, res;
    res = exgcd(b, a % b, x1, y1);
    x = y1, y = x1 - a / b * y1;
    return res;
}

void solve() {
    int a, b;
    cin >> a >> b;
    int ans = 1e10, d;
    int z = b;
    for (; z % 2 == 0; z /= 2);
    for (; z % 5 == 0; z /= 5);
    if (z == 1) {
        cout << "0 1\n";
        return;
    }
    for (int i = 0, pw_2 = 1; i <= 32 && pw_2 * z <= mx; i++, pw_2 *= 2) {
        for (int j = 0, pw_3 = 1; j <= 30 && pw_3 * pw_2 * z <= mx; j++, pw_3 *= 3) {
            int c = a * pw_2 * pw_3;
            if (c * z > mx) continue;
            int x, y;
            exgcd(z, b / z, x, y);
            x *= c, y *= c;
            if (y > 0) y -= y / z * z + z;
            else y += abs(y) / z * z;
            if (ans > abs(y)) ans = abs(y), d = c / a * z;
        }
    }
    cout << ans << " " << d << "\n";
}

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


    int T = 1;
    cin >> T;

    while (T--) {
        solve();
    }
}

/*
4
1 2
2 3
3 7
19 79
 */