#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
const ll INF = 1e9;
const int N = 35;

ll gcd(ll a, ll b) {
    if (!b) return a;
    return gcd(b, a % b);
}

struct info {
    ll p2 = 1, p5 = 1, p = 1;
};

ll pow2[N], pow5[N];
vector<pair<ll, ll>> p25;

void init() {
    pow2[0] = 1;
    pow5[0] = 1;
    for (int i = 1;i <= 30;i++) {
        pow2[i] = pow2[i - 1] * 2LL;
    }
    for (int i = 1;i <= 15;i++) {
        pow5[i] = pow5[i - 1] * 5LL;
    }
    for (int i = 0;i <= 30;i++) {
        if (pow2[i] <= INF) {
            for (int j = 0;j <= 15;j++) {
                if (pow5[j] * pow2[i] <= INF) p25.push_back(make_pair(pow2[i], pow5[j]));
                else break;
            }
        }
        else break;
    }
}

info check(ll x) {
    info res;
    while (x % 2 == 0) {
        res.p2 *= 2LL;
        x /= 2;
    }
    while (x % 5 == 0) {
        res.p5 *= 5LL;
        x /= 5;
    }
    res.p = x;
    return res;
}

void solve()
{
    ll a, b; cin >> a >> b;
    info T = check(b);
    ll P = T.p;
    ll x = T.p2 * T.p5;
    // cout << P << " " <<  T.p2 << " " << T.p5 << '\n';

    if (P == 1) {
        cout << 0 << " " << 1 << '\n';
        return;
    }

    // vector<ll> fct;
    // for (int i = 3;i * i <= P;i++) {
    //     if (P % i == 0) {
    //         fct.push_back(i);
    //         if (P % i != i) fct.push_back(P / i);
    //     }
    // }

    // for (int q : fct) {

    // }
    ll c = INF;
    ll d = 1;
    for (auto& [t2, t5] : p25) {
        if (t2 < T.p2 || t5 < T.p5) continue;
        // t2 /= T.p2, t5 /= T.p5;
        ll tmp = P - ((t2 / T.p2) * (t5 / T.p5) * a % P);
        if (c > tmp) {
            if (t2 * t5 * P <= INF) {d = t2 * t5 * P;c = tmp;}
            
            // cout << t2 << " " << t5 << " " << P << '\n';
        }
    }
    cout << c << " " << d << '\n';
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    init();
    // for (auto [x, y] : p25) {
    //     cout << x << " " << y << '\n';
    // }
    int t; cin >> t;
    while(t--) solve();
    return 0;
};