#include<bits/stdc++.h>
using namespace std;
#define int long long
const int lim=1e9;
int a,b,c,d,x,y;
vector<int> fac[1000005];
void exgcd(int u,int v,int &x,int &y)
{
    if(!v)
    {
        x=1;y=0;
        return;
    }
    exgcd(v,u%v,y,x);
    y-=u/v*x;
}
void sol()
{
    cin>>a>>b;
    c=lim+1;d=lim+1;
    x=1;
    while(b%2==0)
    {
        x*=2;
        b/=2;
    }
    while(b%5==0)
    {
        x*=5;
        b/=5;
    }
    y=b;
    b=x*y;
    if(y==1)
    {
        cout<<"0 1\n";
        return;
    }
    for(int i=1;i*b<=lim;i*=2)
    {
        for(int j=1;i*j*b<=lim;j*=5)
        {
            int now=i*j*b;
            for(auto it:fac[y])
            {
                if(it==1)continue;
                int u=now/(it*i*j);
                int v=y;
                int w=-i*j*a;
                int X,Y;
                int g=gcd(u,v);
                if(w%g)continue;
                exgcd(u,v,X,Y);
                u/=g;v/=g;w/=g;
                X=X*w;
                Y=Y*w;
                int k=Y%u;
                if(k>0)k-=u;
                int nc=X-(k-Y)/u*v;
            //    if(i==1&&j==1)
            //        cerr<<u<<" "<<v<<" "<<w<<" "<<X<<" "<<Y<<" "<<k<<" "<<nc<<endl;
                if(nc<0)
                    nc=nc%v+v;
                if(nc<c)
                {
                    //cerr<<i<<" "<<j<<" "<<it<<endl;
                    c=nc;
                    d=it*i*j;
                }
            }
            //cerr<<i<<" "<<j<<endl;
        }
    }
    cout<<c<<" "<<d<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    for(int i=1;i<=1000000;i++)
    {
        for(int j=i;j<=1000000;j+=i)
        {
            fac[j].push_back(i);
        }
    }
    int t=1;
    cin>>t;
    while(t--)
        sol();
}