#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
#define int ll
using namespace std;
constexpr int N=1e6+7;
constexpr int M=2e3+7;
constexpr int inf=1e9;
int a,b;
int exgcd(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	int x1,y1,d;
	d=exgcd(b,a%b,x1,y1);
	x=y1;
	y=x1-(a/b)*y1;
	return d;
}
int p2[40],p5[30];
void init()
{
    p2[0]=p5[0]=1;
    for(int i=1;i<=30;i++)
    {
        p2[i]=p2[i-1]*2;
    }
    for(int i=1;i<=13;i++)
    {
        p5[i]=p5[i-1]*5;
    }
}
void solve()
{
    cin>>a>>b;
    int p=b;
    while(p%5==0) p/=5;
    while(p%2==0) p/=2;
    int yu=b/p;
    if(p==1) return cout<<"0 1"<<endl,void();
    int c=1e18,d=1;
    for(int i=0;i<=30;i++)
    {
        for(int j=0;j<=13;j++)
        {
            int D=p2[i]*p5[j];
            if(D>inf) break;
            if(D*p>inf) break;
            D=((-D*a%p)%p+p)%p;
            int x,y;
            exgcd(yu,p,x,y);
            int ansc=x*D%p;
            int dd=p2[i]*p5[j]*p;
            if(ansc<c)
            {
                c=ansc;
                d=dd;
            }
        }
    }
    cout<<c<<' '<<d<<endl;
}
signed main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    init();
    int T=1; cin>>T;
    while(T--){solve();}
    return 0;
}