#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b){
    if(a%b==0){
    	return b;
	}
	else{
		return gcd(b,a%b);
	}
}
int main(){
	long long t;
	bool flag;
	cin>>t;
	long long x[t];
	long long z[t];
	for(long long i=0;i<t;i++){
		cin>>x[i]>>z[i];
	}
	for(long long i=0;i<t;i++){
		flag = false;
		for(long long j=0;j<x[i];j++){
			if(x[i]*j*gcd(x[i],j)==z[i]){
				cout<<j;
				flag = true;
				continue;
		    }
		}
		if(flag = false){
			cout<<-1;
		}
	}
	return 0;
}