#include<bits/stdc++.h>
using namespace std;
vector<int>v={2};
void solve(int t)
{
    int n,m; cin>>n>>m;
    int b = min(n,m);
    for(auto x:v)
    {
        if(x>b) break;
        if(n%x==0 && m%x==0)
        {
            cout<<x<<endl;
            return;
        }
    }
    cout<<-1<<endl;
}
int main()
{
    for(int n=3;n<=1000;n++)
    {
        int rt = sqrt(n);
        bool prime=true;
        for(int i=2;i<=rt;i++)
        {
            if(n%i==0)
            {
                prime=false;
                break;
            }
        }
        if(prime) v.push_back(n);
    }

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