#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> prime;
vector<bool> is_not_prime(1e6 + 2);
vector<ll> fac(1e6 + 2);
vector<set<ll> > v(1e6 + 2);
vector<ll> phi(1e6 + 10);
ll qp(ll a, ll b, ll mod){
  ll z = 1;
  while(b){
    if(b & 1) z = z * a % mod;
    b >>= 1;
    a = a * a % mod;
  }
  return z;
}
void solve(){
  ll a, b;
  cin >> a >> b;
  ll curb = b;
  ll num2 = 0;
  ll num5 = 0;
  ll r = 1;
  while(curb % 2 == 0){
    curb /= 2;
    r *= 2ll;
    ++num2;
  }
  while(curb % 5 == 0){
    curb /= 5;
    ++num5;
    r *= 5ll;
  }
  ll b1 = b / r;
  vector<ll> p2(40);
  vector<ll> p5(40);
  p2[0] = p5[0] = 1;
  ll curc = 0x7fffffffff;
  ll curd = 0x7fffffffff;
  for(ll i = 1; i <= 31; ++i){
    p2[i] = p2[i - 1] * 2ll;
  }
  for(ll i = 1; i <= 13; ++i){
    p5[i] = p5[i - 1] * 5ll;
  }
  ll a1 = a / gcd(a, r);
  ll r1 = r / gcd(a, r);
  for(ll i = 0; i <= 31; ++i){
    for(ll j = 0; j <= 13; ++j){
      if(__int128_t(p2[i]) * __int128_t(p5[j]) * __int128_t(b1) > 1e9){
        continue;
      }
      ll cur = p2[i] * p5[j] % b1;
      ll rv = qp(r1, phi[b1], b1);
      ll now = a1 * cur % b1 * rv % b1;
      ll c = (-now + b1) % b1;
      ll d = p2[i] * p5[j] * b1;
      if(c <= curc){
        if(c == curc){
          curd = min(curd, d); 
        }
        else
          curd = d;
        curc = c;
      }
    }
  }
  cout << curc << ' ' << curd << '\n';
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ll t;
  cin >> t;
  for(ll i = 2; i <= 1e6; i++){
    if(!is_not_prime[i]){
      prime.push_back(i);
      fac[i] = i;
    }
    for(ll j : prime){
      if(j * i > 1e6) break;
      is_not_prime[j * i] = true;
      fac[j * i] = j;
      if(i % j == 0) break;
    }
  }
  for(ll i = 2; i <= 1e6; ++i){
    ll val = i;
    while(val > 1){
      v[i].insert(fac[val]);
      val /= fac[val];
    }
  }
  phi[1] = 1;
  for(ll i = 2; i <= 1e6; ++i){
    ll cur = i;
    phi[i] = 1;
    for(auto j: v[i]){
      cur /= j;
      phi[i] *= j - 1;
    }
    phi[i] *= cur;
  }
  while(t--){
    solve();
  }
}