#include <bits/stdc++.h>
#define int long long

using namespace std;

int exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }
    int d = exgcd(b, a % b, x, y);
    int t = x;
    x = y;
    y = t - a / b * y;
    return d;
}

// bool getans(int cur2) {
//     int x, y;
//     exgcd()
// }

void solve() {
    int a, b;
    scanf("%lld%lld", &a, &b);
    int cur = 1;
    int ans = 1000000000, ans2 = 0;
    // int 
    auto getans = [&b, &a](int cur2) -> int {
        int x, y;
        // cerr << b << ' ' << 1 << '\n';
        exgcd(b, 1, x, y);
        y = -y;
        // cerr << x << ' ' << y << '\n';
        x *= cur2 * a;
        y *= cur2 * a;
        y %= b;
        y += b;
        y %= b;
        return y;
    };
    for (int i = 0; i <= 20; ++i) {
        // int cu
        int cur2 = cur;
        for (int j = 0; j <= 20; ++j) {
            int tmp = getans(cur2);
            if (tmp < ans) {
                ans = tmp;
                ans2 = cur2 * b;
            }
            if (cur2 > 1000000000 / (5 * b)) break;
            cur2 *= 5;
        }
        if (cur > 1000000000 / (2 * b)) break;
        cur *= 2;
    }
    printf("%lld %lld\n", ans, ans2);
}

signed main() {
    int T;
    scanf("%lld", &T);
    while (T--) {
        solve();
    }
    return 0;
}