#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long long ll;
typedef __int128 i128;
const int N=2e5+5,M=2e5+5,T=20,mod=998244353,B=131,INF=2e9,P=1000000711;

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,y,x);
    y-=a/b*x;
    return d;
}
void solve(){
    int a,b;
    cin>>a>>b;
    int t1=1,p=b;
    while(p%2==0){
        p/=2;
        t1*=2;
    }
    while(p%5==0){
        p/=5;
        t1*=5;
    }
    pii ans={-1,-1};
    for(int i=0;i<28;i++){
        int t2=1,q=i;
        while(q--)t2*=2;
        for(int j=0;j<13&&p*t2<=1e9;j++,t2*=5){
            int c,k;
            int d=exgcd(-t1,p,c,k);
            c=(a*t2/d)%mod*c%mod;
            c=(c%p+p)%p;
            if(ans.first==-1||c<ans.first)
                ans={c,t2*p};
        }
    }
    cout<<ans.first<<" "<<ans.second<<endl;
}
void fast(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
}
signed main(){
    fast();
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}