//....................................<In the name of Allah>...............................//

//.................................<b_bitsmillahir Rahmanir Rahim>...................................//
// Author : Riaj Udd_bitn

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll, ll> pii;
typedef pair<double, double> pdd;

typedef double dl;

#define lower(a, b) lower_bound((a).begin(), (a).end(), b) - (a).begin()
#define mem(a, b) memset(a, b, sizeof(a));

#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()

#define fraction(a)               \
    cout.unsetf(ios::floatfield); \
    cout.precision(a);            \
    cout.setf(ios::fined, ios::floatfield);
//////////////////////////////////////////
template <typename F, typename S>
ostream &operator<<(ostream &os, const pair<F, S> &p)
{
    return os << "(" << p.first << ", " << p.second << ")";
}

template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v)
{
    os << "{";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "}";
}

template <typename T>
ostream &operator<<(ostream &os, const set<T> &v)
{
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "]";
}

template <typename T>
ostream &operator<<(ostream &os, const multiset<T> &v)
{
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << *it;
    }
    return os << "]";
}

template <typename F, typename S>
ostream &operator<<(ostream &os, const map<F, S> &v)
{
    os << "[";
    for (auto it = v.begin(); it != v.end(); ++it)
    {
        if (it != v.begin())
            os << ", ";
        os << it->first << " = " << it->second;
    }
    return os << "]";
}

#define dbg(args...)            \
    do                          \
    {                           \
        cerr << #args << " : "; \
        faltu(args);            \
    } while (0)

void faltu()
{
    cerr << endl;
}

template <typename T>
void faltu(T a[], ll n)
{
    for (ll i = 0; i < n; ++i)
        cerr << a[i] << ' ';
    cerr << endl;
}

template <typename T, typename... hello>
void faltu(T arg, const hello &...rest)
{
    cerr << arg << ' ';
    faltu(rest...);
}

///////////b_bitt-manipulation///////////////
#define Mb(msk) 63 - __builtin_clzll(msk)
#define Lb(msk) __builtin_ctzll(msk)
#define ONE(msk) __builtin_popkll(msk)
#define CHECK(msk, b_bitt) (msk & (1LL << b_bitt))
#define ON(msk, b_bitt) (msk | (1LL << b_bitt))
#define Off(msk, b_bitt) (msk & ~(1LL << b_bitt))
#define CHANGE(msk, b_bitt) (msk ^ (1LL << b_bitt))

//////////////

void solve(int tc)
{
    int n, m;
    cin >> n >> m;

    int gc = __gcd(n, m);
    int get = gc;
    for (int i = 2; i * i <= gc; i++)
    {
        if (gc % i == 0)
        {
            get = i;
            break;
        }
    }
    cout << (get == 1 ? -1 : get) << "\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1, cs = 0;
    cin >> t;
    for (int tc = 1; tc <= t; tc++)
    {
        solve(tc);
    }
}