#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int T;
ll a, b, c, d;
int cp2, cp5;
ll ip2, ip5;

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

ll inv(ll a, ll p) {
    ll x, y;
    exgcd(a, p, x, y);
    x = (x % p + p) % p;
    return x;
}

int main() {
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &a, &b);
        cp2 = cp5 = 0;
        for (; b % 2 == 0; b /= 2, cp2++);
        for (; b % 5 == 0; b /= 5, cp5++);
        if (b == 1) {
            puts("0 1");
            continue;
        }
        ip2 = ip5 = 1ll;
        for (int i = 0; i < cp2; i++, ip2 *= inv(2, b));
        for (int i = 0; i < cp5; i++, ip5 *= inv(5, b));
        c = 1e9 + 1ll;
        for (int i = 0; i < 35; i++) {
            for (int j = 0; j < 15; j++) {
                ll tmp = (-a % b + b) % b, tmp2 = b;
                for (int k = 0; (k < i) && (tmp2 <= 1e9); k++, tmp2 *= 2);
                for (int k = 0; (k < i) && (tmp2 <= 1e9); k++, tmp2 *= 5);
                if (tmp2 > 1e9) continue;
                for (int k = 0; k < i; k++, tmp *= 2, tmp %= b);
                for (int k = 0; k < j; k++, tmp *= 5, tmp %= b);
                if (tmp < c) {
                    c = tmp;
                    d = tmp2;
                }
            }
        }
        printf("%lld %lld\n", c, d);
    }
    return 0;
}