#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define endl '\n'
// #define int long long
#define rep(i, j, k) for(int i = j; i <= k; ++ i)
using namespace std;
int Mod;
const int INF = 1e9;
int tot = 0;
int pow5[35], po5 = 0, ydbs[255], po2 = 0, pow2[35];
int fpow(int a, int b){
	int x = 1;
	while(b){
		if(b & 1) x = 1ll * x * a % Mod;
		a = 1ll * a * a % Mod;
		b >>= 1;
	}
	return x;
}
void solve(){
	int a, b;
	cin >> a >> b;
	int t1 = 0, t2 = 0, t, x = 1, y = 1, z = 1;
	while(b % 2 == 0){
		t1++;
		b /= 2;
		x *= 2;
	}
	while(b % 5 == 0){
		t2++;
		b /= 5;
		x *= 5;
	}
	if(b == 1){
		cout << 0 << " " << 1 << endl;
		return;
	}
	t = max(t1, t2); 
	Mod = b;
	int tt = b, phi = b;
	for(int i =  2; i <= sqrt(tt); ++ i){
		if(tt % i == 0){
			phi /= i;
			phi *= (i - 1);
			while(tt % i == 0) tt /= i;
		}
	}
	if(tt){
		phi /= tt;
		phi *= (tt - 1);
	}
	// y = fpow(10, t);
	// z = y * fpow(x, phi - 1) % Mod;
	int tar = 1ll * a * fpow(x, phi - 1) % Mod;
	// cout << tar << endl;
	tar = Mod - tar;
	int minn = 1e9, mind = 1;
	int SX = INF / b;
	rep(i, 1, tot){
		if(ydbs[i] > SX) break;
		int tx = 1ll * tar * ydbs[i] % Mod;
		if(minn > tx){
			minn = tx;
			mind = ydbs[i];
		}
		if(minn == 1) break;
	}
	cout << minn << " " << mind * b << endl;
}
signed main(){
	ios::sync_with_stdio(0);
	pow5[0] = 1;
	while(pow5[po5] <= INF / 5) {
		++po5;
		pow5[po5] = pow5[po5 - 1] * 5;
	}
	// po5--;
	pow2[0] = 1;
	while(pow2[po2] <= INF / 2){
		++po2;
		pow2[po2] = pow2[po2 - 1] << 1;
	}
	// po2 --;
	int x = 1;
	while(x <= INF){
		rep(i, 0, po5){
			if(1ll * x * pow5[i] > INF) break;
			ydbs[++tot] = x * pow5[i];
		}
		x <<= 1;
	}
	sort(ydbs + 1, ydbs + tot + 1);
	// cout << tot << endl;
	int T;
	cin >> T;
	while(T--) solve();
}