#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int ipt,x,t;
	cin >> ipt;
	vector<int>XI;
	while (ipt != 0)
	{
		int x,t;
		cin >> x;
		cin >> t;
		if(x < 0 || t < 0)
		{
			return 0;
		}
		for(int j = 2; j < t; j++)
		{
			if(j % x == 0 && j % t == 0)
			{
				x /= j;
				t /= j;
				XI.push_back(j);
			}
			else
			{
				XI.push_back(1);
			}
		}
 
		ipt--;
	}
	return 0;
}
 
				CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPHZlY3Rvcj4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCWludCBpcHQseCx0OwoJY2luID4+IGlwdDsKCXZlY3RvcjxpbnQ+WEk7Cgl3aGlsZSAoaXB0ICE9IDApCgl7CgkJaW50IHgsdDsKCQljaW4gPj4geDsKCQljaW4gPj4gdDsKCQlpZih4IDwgMCB8fCB0IDwgMCkKCQl7CgkJCXJldHVybiAwOwoJCX0KCQlmb3IoaW50IGogPSAyOyBqIDwgdDsgaisrKQoJCXsKCQkJaWYoaiAlIHggPT0gMCAmJiBqICUgdCA9PSAwKQoJCQl7CgkJCQl4IC89IGo7CgkJCQl0IC89IGo7CgkJCQlYSS5wdXNoX2JhY2soaik7CgkJCX0KCQkJZWxzZQoJCQl7CgkJCQlYSS5wdXNoX2JhY2soMSk7CgkJCX0KCQl9CgkJCgkJaXB0LS07Cgl9CglyZXR1cm4gMDsKfQo=