#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;
}