#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=