一开始的想法是枚举gcd，时间复杂度O（T*sqrt（x)*log2(x）），两个大样例跑了0.5s，后面想了一个小时也没什么好思路，一直在往扩欧那边想......

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
inline ll read(){
  ll xh=0,kh=1;char ch=getchar();
  while(ch<'0'||ch>'9'){if(ch=='-')kh=-1;ch=getchar();}
  while(ch>='0'&&ch<='9'){xh=(xh<<3)+(xh<<1)+(ch^48);ch=getchar();}
  return xh*kh;
}
inline void write(ll xh) {
  if(xh<0){putchar('-');xh=-xh;}
  if(xh>=10)write(xh/10);
  char ch=(xh%10)^48;putchar(ch);
}
ll n, m, T, x, y, temp, ans = 0, z;
inline ll gcd(ll a, ll b) {return a % b == 0 ? b : gcd(b, a % b);}
int main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	T = read();
	while(T--) {
	  x = read(); z = read();
	  ans = 0;
	  if(z % x) {
	    write(-1);
	    printf("\n");
	    continue;
	  }
	  for(ll i = 1; i * i <= x; i++) {
	    if(x % i) continue;
	    if(z % (x * i) == 0)
		  if(gcd(x, z / x / i) == i) {
	        ans = z / x / i;
	        break;
	      }   
	    if(z % (x * x * i) == 0)
		  if(gcd(x, z / x / x / i) == x / i) 
		    ans = max(ans, z / x / x / i);
	  }
	  if(!ans) {
	  	write(-1);
	  	printf("\n");
	  }
	    else {
	    write(ans);
	    printf("\n");
	  }
	}
	return 0;
}