#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define int ll
vector<ll> k;
inline int exgcd(int a, int b, int &x, int &y, int t) {
    if (b == 0) {
        x = t, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y, t);
    int z = x;
    x = y, y = z - y * (a / b);
    return d;
}
void slove() {
    ll up = 1e9;
    ll a, b;
    cin >> a >> b;
    int bb = b;
    while (bb % 2 == 0) bb /= 2;
    while (bb % 5 == 0) bb /= 5;
    int k1 = b / bb;
    if (bb == 1) {
        cout << "0 1\n";
        return;
    }
    int C = 1e18, D = 0;
    for (int i = 0; i < k.size(); i++) {
        int k2 = k[i];
        int t = (-(a * k2) % bb + bb) % bb;
        int x, y;
        int gcd = exgcd(k1, bb, x, y, t);
        int lcm = bb / gcd;
        int c = x % lcm;
        if (c < C) {
            C = c, D = bb * k2;
        }
    }
    cout << C << ' ' << D << endl;
}

signed main() {
    ll up = 1e9;

    for (ll i = 1; i <= (ll)1e9; i *= 2LL) {
        ll tmp = i;
        while (tmp <= up) {
            k.push_back(tmp);
            tmp *= 5LL;
        }
    }

    //    cout << k.size() << endl;
    int cnt = 1;
    cin >> cnt;

    while (cnt--) {
        slove();
    }

    return 0;
}
/*
4
1 2
2 3
3 7
19 79
*/