#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define pb emplace_back
#define inf 0x3f3f3f3f3f3f3f3fll
const int maxn=1e9;
int rd()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9')
	{
		if(c=='-') f=-f;
		c=getchar();
	} 
	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c&15),c=getchar();
	return f*x;
}
int x,y;
void exgcd(int a,int b)
{
	if(!b)
	{
		x=1,y=0;
	}
	else
	{
		exgcd(b,a%b);
		int t=x;
		x=y;
		y=t-a/b*y;
	}
}
void chkmin(int &a,int b){a=a<b?a:b;}
void chkmax(int &a,int b){a=a>b?a:b;}
void work()
{
	int a=rd(),b=rd(),c=maxn,d=maxn;
	int bb=b;
	while(bb%2==0) bb>>=1;
	while(bb%5==0) bb/=5;
	if(bb==1)
	{
		puts("0 1");
		return ;
	}
	int k=b/bb;
	exgcd(k,bb);
	int invk=(x%bb+bb)%bb;
	// cerr<<invk<<endl;
	for(int p2=1;p2<=maxn;p2<<=1)
	{
		for(int p5=1;p2*p5<=maxn;p5*=5)
		{
			int dd=bb*p2*p5;
			int cc=((-a*p2*p5*invk)%bb+bb)%bb;
			if(cc<c||(cc==c&&dd<d)) c=cc,d=dd;
		}
	}
	printf("%lld %lld\n",c,d);
}
signed main()
{
	int T=rd();
	while(T--) work();
	return 0;
}