#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>

using namespace std;


int main(){
	long long t;
	cin >> t;
	while(t){
		long long x,z;
		cin >> x >> z;
		long long d=sqrt(__gcd(x*x,z/x));
		long long flag=0;
		for(long long q=1;(x*d*q*d)<=z;q++){
			if(x*(q*d)*__gcd(x,q*d)==z){
				printf("%d\n",q*d);
				flag=1;
				break;
			}
		}
		if(!flag) printf("-1\n");
		t--;
	}
	return 0;
}