#include <bits/stdc++.h>
using namespace std;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T;
	cin >> T;
	while (T--)
	{
		long long a, b;
		cin >> a >> b;
		long long z = b;
		while (z % 2 == 0)
			z /= 2;
		while (z % 5 == 0)
			z /= 5;
		vector<long long> p2(30);
		vector<long long> p5(13);
		p2[0] = p5[0] = 1;
		for (int i = 1; i <= 29; ++i)
			p2[i] = p2[i - 1] * 2;
		for (int i = 1; i <= 12; ++i)
			p5[i] = p5[i - 1] * 5;
		auto exgcd = [&](auto self, long long a, long long b, long long &x, long long &y) -> long long
		{
			if (b == 0)
			{
				x = 1;
				y = 0;
				return a;
			}
			long long d = self(self, b, a % b, y, x);
			y -= a / b * x;
			return d;
		};
		long long ansc = 1e9, ansd;
		for (int i = 0; i <= 29; ++i)
			for (int j = 0; j <= 12; ++j)
			{
				if (p2[i] * p5[j] * z > 1e9)
					break;
				long long k = p2[i] * p5[j];
				long long d = k * z;
				long long g = gcd(b, d);
				long long A = b / g;
				long long B = z;
				long long C = -a * (d / g);
				long long c, y;
				long long D = exgcd(exgcd, A, B, c, y);
				c = ((c * (C / D)) % (B / D) + (B / D)) % (B / D);
				if (c < ansc)
					ansc = c, ansd = d;
			}
		cout << ansc << " " << ansd << "\n";
	}
}

/*
4
1 2
2 3
3 7
19 79
*/