#include <bits/stdc++.h>

using namespace std;


using i64 = long long;

const i64 MAXN = 2e9;
const i64 inf = LLONG_MAX / 2;

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

i64 calc(i64 a, i64 b, i64 c) {
	i64 x, y;
	i64 d = exgcd(a, b, x, y);
	d = abs(d);
	if(c % d != 0) return inf;
	x *= c / d;
	i64 t = abs(b / d);
	return (x % t + t) % t;
}

void solve() {
	i64 a, b;
	cin >> a >> b;

	i64 w = b;
	while(w % 2 == 0) w /= 2;
	while(w % 5 == 0) w /= 5;
	
	if(w == 1) {
		cout << "0 1\n";
		return;
	}

	i64 resc = inf, resd;
	for(i64 p5 = w; p5 <= MAXN; p5 *= 5)
		for(i64 d = p5, c; d <= MAXN; d *= 2) {
			c = calc(b, w * w, -a * d);
			if(c < resc) resc = c, resd = d;
		}
	cout << resc << " " << resd << "\n";
	return;
}

int main() {
	int T;
	cin >> T;

	while(T --)
		solve();

	return 0;
}