/*
 *   Copyright (c) 2024 Emon Thakur
 *   All rights reserved.
 */
#include<bits/stdc++.h>
using namespace std;
void solve()
{
    int n,m; cin>>n>>m;
    int a=min(n,m);
    int b=sqrt(a);
    int ans = 1e9;
    for(int i=2;i<=b;i++)
    {
        if(n%i==0 && m%i==0)
        {
            ans = min(ans,i);
        }
        else if(n%(a/i)==0 && m%(a/i)==0)
        {
            ans = min(ans,a/i);
        }
    }
    if(max(n,m)%a==0 && a!=1) ans = min(a,ans);
    if(ans!=1e9) cout<<ans<<endl;
    else cout<<-1<<endl;
}

int main()
{
    int t; cin>>t; while(t--) solve();
}