#include<bits/stdc++.h>
#define ll long long
#define db double
#define tp ll
#define ptp pair<tp,tp>
#define pdb pair<db,db>
#define umap unordered_map
#define ed '\n'

using namespace std;

vector<tp>bs;
tp a, b;

tp gcd(tp a, tp b) {
    if (a < b) swap(a, b);
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

inline tp exgcd(const tp a, const tp b, tp& x, tp& y) {
    if (b == 0) return x = 1, y = 0, a;
    tp d = exgcd(b, a % b, y, x);
    y -= a / b * x; return d;
}

void init() {
    tp tmp = 1;
    while (tmp <= 1e9) {
        bs.push_back(tmp);
        tmp *= 2;
    }
    tp sz = bs.size();
    for (tp i = 0; i < sz; i++) {
        tmp = bs[i];
        tp lim = 1e9;
        while (tmp * 5 <= lim) {
            tmp *= 5;
            bs.push_back(tmp);
        }
    }
    sort(bs.begin(), bs.end());
}

void clear() {
}

void solve() {
    cin >> a >> b;
    tp b1 = b;
    while (b1 % 2 == 0) {
        b1 /= 2;
    }
    while (b1 % 5 == 0) {
        b1 /= 5;
    }
    if (b1 == 1) {
        cout << "0 1" << ed;
        return;
    }
    tp ansc = 2e9, ansd = 2e9;
    for (auto i : bs) {
        tp d = i * b1;
        if (d > 1e9) {
            continue;
        }
        tp fm = (d * b) / gcd(b, d);
        tp num = (fm / b) * a;
        tp k1 = (fm / d);
        //num+k1*c==k2*b1
        //k1*c+b1*(-k2)==(-num)
        //k1*(-c)+b1*k2==num
        tp c = 0, k2 = 0;
        exgcd(k1, b1, c, k2);
        c = -c;
        if ((num * c) % gcd(k1, b1) != 0) {
            continue;
        }
        c = (c * num / gcd(k1, b1));
        tp dis = b1 / gcd(k1, b1);
        if (c < 0) {
            c += (((-c - 1) / dis + 1) * dis);
        }
        if (ansc > c) {
            ansc = c;
            ansd = d;
        }
    }
    cout << ansc << ' ' << ansd << ed;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    init();
    int _t = 0;
    cin >> _t;
    while (_t--) {
        solve();
    }
}
/*

4
1 2
2 3
3 7
19 79


*/