#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
const int N=1e3+5,inf=1e9;
int q[N],tot;
map<int,int> mp;
void dfs(int x){
	if(x>inf)
		return ;
	if(!mp[x]){
		mp[x]=1;
		q[++tot]=x;
	}
	dfs(x*2);
	dfs(x*5);
}
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1;
		y=0;
		return ;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
void solve(){
	int a,b;
	cin>>a>>b;
	int B=b;
	while(B%2==0)
		B/=2;
	while(B%5==0)
		B/=5;
	if(B==1){
		cout<<"0 1\n";
		return ;
	}
	int ans1=inf,ans2=inf,w=b/B;
	for(int i=1;i<=tot&&q[i]*B<=inf;i++){
		int d=q[i]*B;
		//xc=y(modB) -> xc+Bk=y
		int y=(-(q[i]*a)%B+B)%B,x=w,X,Y;
		exgcd(x,B,X,Y);
		X=(X%B+B)%B;
		int c=X*y%B;
		if(ans1>c){
			ans1=c;
			ans2=d;
		}
	}
	cout<<ans1<<" "<<ans2<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie();cout.tie();
	dfs(2);
	dfs(5); 
	sort(q+1,q+1+tot);
	int T;cin>>T;
	while(T--)
		solve();
	return 0;
}
/*
4
1 2
2 3
3 7
19 79 
*/