记录

代码：

#include <bits/stdc++.h> 

long long gcd(long long a, long long b)
{
	if(a % b == 0)
	{
		return b;
	}
	
	return gcd(b, a % b);
}

int main()
{
	long long T;
	
	
	scanf("%d", &T);
	
	while(T--)
	{
		long long x, y = INT_MAX, z;
		
		scanf("%d %d", &x, &z);
		
		for(long long i = sqrt(z/x); i <= z/x; i++)
		{
			if(z == x * i * gcd(x, i))
			{
				y = i;
				break;
			}
		}
		if(x == z)
		{
			y = 1;
		}
        
        if(y == INT_MAX) 
        {
        	printf("%d\n", -1);
		}
		else
		{
        	printf("%d\n", y);
		}
	}
	return 0;
}