#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 x,y;
void exgcd(int a,int b)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b);
	int t=x;
	x=y;
	y=t-a/b*y;
}
int exgcd1(int a,int b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	int x1,y1,d;
	d=exgcd1(b,a%b,x1,y1);
	x=y1;
	y=x1-(a/b)*y1;
	return d;
}
int p5[37],p2[37];
void init()
{
	p2[0]=p5[0]=1;
	for(int i=1;i<=32;i++)
	{
		p2[i]=p2[i-1]*2;
	}
	for(int i=1;i<=17;i++)
	{
		p5[i]=p5[i-1]*5;
	}
}
void solve()
{
	int a,b;
	cin>>a>>b;
	int p=b;
	while(p%5==0) p/=5;
	while(p%2==0) p/=2;
	if(p==1) return cout<<"0 1"<<endl,void();
	exgcd(b/p,p);
	x=(x%p+p)%p; // x 为 b/p 的逆元
	int c=inf,d;
	for(int i=0;i<=30;i++)
	{
		for(int j=0;j<=13;j++)
		{
			int cur_d=p2[i]*p5[j];  // d/p
			if(cur_d>inf) break;
			int tmp=((-((a*cur_d*x)%p))%p+p)%p;
			int cur_x,cur_y;
			exgcd1(1,p,cur_x,cur_y);
			cur_x=((cur_x*tmp)%p+p)%p; // c
			if(cur_x<c)
			{
				c=cur_x;
				d=cur_d*p;
			}
		}
	}
	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;
}