#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000010;
const int mx = 1000000000;

int T, a, b, c, d, x, y, pw2[N], pw5[N], rs[N], cnt, ans, ansr;

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;
}

void solve()
{
    ans = mx + 1;
    scanf("%lld%lld", &a, &b);
    int k = 1;
    while(b % 2 == 0) k *= 2, b /= 2;
    while(b % 5 == 0) k *= 5, b /= 5;
    if(b == 1) return puts("0 1"), void();
    int t = 1;
    for(int i = 1; i <= cnt; i++){
        t = rs[i];
        if(t * b > mx) continue;
        long long val = 1ll * a * t % b;
        val = b - val;
        Exgcd(k, b, x, y);
        val = 1ll * x * val % b;
        if(val < ans) ans = val, ansr = b * t;
    }
    printf("%lld %lld\n", ans, ansr);
}

signed main()
{
    pw2[0] = pw5[0] = 1;
    for(int i = 1; i < 30; i++) pw2[i] = pw2[i - 1] * 2;
    for(int i = 1; i < 13; i++) pw5[i] = pw5[i - 1] * 5;
    for(int i = 0; i <= 29; i++){
        for(int j = 0; j <= 12; j++){
            long long r = 1ll * pw2[i] * pw5[j];
            if(r <= mx) rs[++cnt] = r;
        }
    }
    sort(rs + 1, rs + cnt + 1);

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