#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pii pair<int,int>
#define fi first
#define se second
//cout<<setiosflags(ios::fixed)<<setprecision(K);
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
const double eps=1e-9; 
const double PI=acos(-1.0);
const int inf=1e9+7;
const int mod=998244353;
const int N=2e5+10,M=N<<1;

#define int long long
vector<int>v;
void init(){
    int b=1;
    for(int i=0;i<=30;i++){
        int c=1;
        for(int j=0;j<20&&b*c<=1e9;j++){
            int t=b*c;
            if(t<=1e9) v.push_back(t);
            c*=5;
        }
        b*=2;
    }
    sort(v.begin(),v.end());
}

ll gcd(ll a,ll b){
    if(b==0) return a;
    return gcd(b,a%b);
}
//d为gcd(a,b)
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1,y=0;
        return a;
    }
    ll x1,y1,d;
    d=exgcd(b,a%b,x1,y1);
    x=y1,y=x1-a/b*y1;
    return d;
}

void solve(){
    int a,b;
    cin>>a>>b;
    int t=1;
    while(b%5==0) b/=5,t*=5;
    while(b%2==0) b/=2,t*=2;
    if(b==1){
        cout<<0<<' '<<1<<'\n';
        return;
    }

    int c=b-a%b;
    int cd=b*t;
    //cerr<<c<<' '<<cd<<'\n';

    for(auto x:v){
        int d=x*b;
        if(d>1e9) continue;
        //ax+ct/b

        int y;
        if(a*x%b==0) y=0;
        else y=b-a*x%b;

        int cur=0;

        int n,m;
        int rd=exgcd(t,b,n,m);
        if(y%rd==0){
            int rc=n*y/rd%b;
            if(rc<=c){
                c=rc;
                cd=d;
            }
        }
    }
    cout<<c<<' '<<cd<<'\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    init();
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}