#include<bits/stdc++.h>

//#include <Windows.h> Sleep(300);
using namespace std;
#define int long long
#define endl '\n'
#define vi vector<int>
#define pii pair<int, int>
#define pb push_back
#define mod 1000000007
#define log(args...){ string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); cout<<endl; }

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cout << *it << " = " << a << " ";
	err(++it, args...);
}
#define fr(i, n) for(int i=0; i<n; i++)
#define fr1(i, n) for(int i=1; i<=n; i++)
#define fab(i, a, b) for(int i=a; i<b; i++)
const int dx[]={+1,-1,+0,+0};
const int dy[]={+0,+0,+1,-1};

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t; cin>>t;
    while(t--){
        int a, b; cin>>a>>b;
        set<int> st;
        for(int i=1; i*i<=a; i++) {
            if(a%i==0){
                if(i!=1) st.insert(i);
                st.insert(a/i);
            }
        }
        //for(auto x: st) log(x);
        int mini = INT_MAX;
        for(int i=1; i*i<=b; i++){
            if( b%i==0){
                if(st.count(i)) mini = min(mini, i);
                if(st.count(b/i)) mini = min(mini, b/i);
            }
        }
        cout<<(mini==INT_MAX ? -1 : mini)<<endl;
    }

}