#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define int ll
vector<ll> k;
inline int exgcd(int a,int b,int &x,int &y)
{
    if(b==0) {x=1,y=0; return a;}
    int d=exgcd(b,a%b,x,y);
    int z=x;
    x=y, y=z-y*(a/b);
    return d;
}
void slove(){
    ll up = 1e9;
    ll a, b;
    cin >> a >> b;
    int bb=b;
    while(bb % 2 == 0) bb /= 2;
    while(bb % 5 == 0) bb /= 5;
    int k1=b/bb;
    if (bb == 1) {
        cout << "0 1\n";
        return ;
    }
    int C=1e18,D=0;
    for (int i = 0 ; i < k.size() ; i++){
        int k2=k[i];
        int t=(-(a*k2)%bb+bb)%bb;
        int x, y;
        int gcd=exgcd(k1,bb,x,y);
        int lcm=bb/gcd;
        int c=x%lcm;
        if(c<C) {C=c, D=bb*k2;}
    }
    cout<<C<<' '<<D<<endl;
}

signed main(){
   ll up = 1e9;

   for (ll i = 1 ; i <= (ll)1e9 ; i *= 2LL){
       ll tmp = i;
       while(tmp <= up){
          k.push_back(tmp);
          tmp *= 5LL;
       }
   }

//    cout << k.size() << endl;
   int cnt = 1;
   cin >> cnt;

   while(cnt--) {
    slove();
   }

   return 0;
}
/*
4
1 2
2 3
3 7
19 79
*/