#include<iostream>
#include<cstdio>
#include<cstring>
#define I inline
#define int long long
using namespace std;

I void exgcd(int a,int b,int &x,int &y){
	if(b==0) {
		x=1,y=0; 
		return ;
	}
	exgcd(b,a%b,x,y);
	int d=x;
	x=y,y=d-a/b*y;
} 
int gcd(int x,int y) {
	if(!y) return x;
	return gcd(y,x%y);
}
I void solve() {
	int a,b; cin>>a>>b;
	int rev=b;
	while(rev%2==0) rev/=2;
	while(rev%5==0) rev/=5;
	int ansc=1e9+1,ansd=0;
	for(int d=rev;d<=1e9;d*=2) {
		for(int nd=d;nd<=1e9;nd*=5) { //cout<<nd<<endl;
			int nk=0,nc=0,g=gcd(rev*rev,b),B=rev*rev/g,C=-a*d;
			if(C%g) continue;
			C/=g;
			exgcd(b/g,B,nc,nk);
			int mnc=(nc*C%B+B)%B;
			if(mnc<ansc) {
				ansc=mnc;
				ansd=nd;
			}
		}
	}
	cout<<ansc<<' '<<ansd<<endl;
}
/*
4
1 2
2 3
3 7
19 79

*/

signed main()
{
	int T; cin>>T;
	while(T--) {
		solve();
	}	
}