#include <bits/stdc++.h>
using namespace std;

#define int long long

int exgcd(int a, int b, int &x, int &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}
// ax + by = c, 可求解线性同余方程 ax === b (mod c)
bool liEu(int a, int b, int c, int &x, int &y)
{
    int d = exgcd(a, b, x, y);
    if (c % d != 0)
        return false;
    int k = c / d;
    x *= k;
    y *= k;
    return true;
}

const int inf = 1e9;

void solve()
{
    int a, b;
    cin >> a >> b;

    int tb = b;
    while (tb % 2 == 0)
    {
        tb /= 2;
    }
    while (tb % 5 == 0)
    {
        tb /= 5;
    }

    auto calc = [&](int d)
    {
        int z = (d * a + tb * tb - 1) / (tb * tb) * (tb * tb) - d * a;
        int x, y;
        liEu(b, tb * tb, z, x, y);
        if (x < 0)
        {
            int tx = x;
            int f = (tb * tb) / gcd(tb * tb, b);
            x += 2 * (abs(x) + f - 1) / f * f;
            x %= f;
        }
        return x;
    };

    int ans = 1e18, ansd;
    for (int i = tb; i <= inf; i *= 5)
    {
        for (int j = i; j <= inf; j *= 2)
        {
            if (ans > calc(j)) {
                ans = calc(j), ansd = j;
            }
        }
    }

    cout << ans << " " << ansd << "\n";
}

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

    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}