#include <bits/stdc++.h>
#define ll long long
#define LL long long
#define ls p<<1
#define rs p<<1|1
#define Ma 1000005
#define mod 1000000007
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define N 61
#define pb push_back
#define ld long double
#define all(x) x.begin(),x.end()
#define inf 1e9

using namespace std;



ll exgcd(ll a,ll b,ll &x,ll &y){
	if (!b)
	{
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b,a%b,y,x);
	y-=a/b*x;
	return d;
}


ll pw;
vector <ll> v;
ll c,di;


ll lcm(ll x,ll y)
{
	return x*y/__gcd(x,y);
}



void go(ll a,ll b,ll d)
{
	ll lc=lcm(b,d);
	a*=lc/b;
	ll mul=lc/d;
	ll x,y;
	ll g=exgcd(pw,mul,x,y);// c=(pw*k-a)/mul
	if (a%g)
		return;
	y*=a/g;
	y=-y;
	y%=pw*mul/g;
	if (y<0)
		y+=pw*mul/g;
	//ll gc=__gcd(y,d);
	//y/=gc,d/=gc;
	//printf("c=%lld d=%lld\n",y,d);
	if (y<c)
		c=y,di=d;
}

void sol()
{
	ll a,b;
	cin>>a>>b;
	a%=b;
	pw=b;
	c=inf;
	while (pw%2==0)
		pw/=2;
	while (pw%5==0)
		pw/=5;
	for (ll i=1;pw*i<=inf;i*=2)
	{
		for (ll j=1;pw*i*j<=inf;j*=5)
		{
			go(a,b,pw*i*j);
		}
	}
	printf("%lld %lld\n",c,di);
	return;
}

int main()
{
	
	IOS
	ll tt=1;
	cin>>tt;
	while (tt--)
		sol();
	return 0;
}


/*

4
1 2
2 3
3 7
19 79

*/