#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll t;
ll gcd(ll x,ll y){
	if(y==0){
		return x;
	}
	return gcd(y,x%y);
}
int main(){
	//freopen("math.in","r",stdin);
	//freopen("math.out","w",stdout);
	scanf("%lld",&t);
	while(t--){
		ll x,z;
		scanf("%lld%lld",&x,&z);
		ll s=z/x;
		bool flag=0;
		for(ll i=sqrt(s);i>=1;i--){
			if(s%i==0&&gcd(x,s/i)==i){
				printf("%lld\n",s/i);
				flag=1;
				break;
			}
		}
		if(!flag){
			printf("-1\n");
		}
	}
	//fclose(stdin);
	//fclose(stdout);
    return 0;
}