#include <bits/stdc++.h>
using namespace std;

long long t, x, z;

long long g(long long a, long long b)
{
	while (b)
	{
		long long temp = a;
		a = b;
		b = temp % b;
	}
	return a;
}

long long sg(long long x, long long y, long long p)
{
	p--;
	long long t = min(x, y), k = 2, sa = 0;
	for (k; k * k <= t; k++)
	{
		if (x % k == 0 and y % k == 0)
		{
			sa++;
			if (sa == p) return g(x / k, y / k);
		}
	}
	return 1;
}

inline long long read()
{
	char ch = getchar();
	long long z = 0;
	while (ch < '0' || ch > '9') ch = getchar();
	while (ch >= '0' and ch <= '9')
	{
		z = (z << 1) + (z << 3) + (ch ^ 48);
		ch = getchar();
	}
	return z;
}

int main()
{
	//freopen("math.in", "r", stdin);
	//freopen("math.out", "w", stdout);
	t = read();
	while (t--)
	{
		x = read(), z = read(); 
		long long b = z / x, res = b / g(x, b);
		if (x * res * g(x, res) != z)
		{
			long long sa = 2;
			while (sa <= 45)
			{
				res = b / sg(x, b, sa);
				if (x * res * g(x, res) == z) break;
				sa++;
			}
		}
		if (x * res * g(x, res) == z) printf("%lld\n", res);
		else puts("-1");
	}
	return 0;
}

赛时写了个这个，大样例是对的，跑得很快，但是这个方法是不是有问题？因为我总感觉这份代码解释不清。