//  _____   _   _____    _____   _____   _      __    __
// |  ___| | | |  _  \  | ____| |  ___| | |     \ \  / /
// | |__   | | | |_| |  | |__   | |__   | |      \ \/ /
// |  __|  | | |  _  /  |  __|  |  __|  | |       \  /
// | |     | | | | \ \  | |___  | |     | |___    / /
// |_|     |_| |_|  \_\ |_____| |_|     |_____|  /_/
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define lowbit(i) ((i) & -(i))
#define ull unsigned long long
#define int long long
// #define i64 long long
#define endl '\n'
using namespace std;
const int inf = 1e9;
vector<int> k;
void init()
{
    for (int i = 1; i <= inf; i *= 2)
        for (int j = 1; j * i <= inf; j *= 5)
            k.push_back(i * j);
    sort(all(k));
}
int Lcm(int a, int b)
{
    return a / __gcd(a, b) * b;
}
template <typename T>
inline T ksm(T base, int n, int mod)
{
    T res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = (res * base) % mod;
        base = (base * base) % mod;
        n >>= 1;
    }
    return res;
}
void solve()
{
    int n, m;
    cin >> n >> m;
    int x = m;
    while (x % 2 == 0)
        x /= 2;
    while (x % 5 == 0)
        x /= 5;
    if (x == 1)
    {
        cout << "0 1\n";
        return;
    }
    int ans = inf, ansd = 0;
    for (int i = 0; i < k.size(); i++)
    {
        int d = k[i] * x;
        if (d > inf)
            break;
        int g = __gcd(m, d);
        int c = ksm(m / g, x - 2, x) * (-(n * d / g) % x + x) % x;
        if (c < ans)
            ans = c, ansd = d;
    }
    cout << ans << ' ' << ansd << endl;
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int tt = 1;
    cin >> tt;
    init();
    while (tt--)
    {
        solve();
    }
    return 0;
}