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

vector<string> strings{
        "RGB",
        "GRB",
        "GBR",
        "BGR",
        "BRG",
        "RBG"
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t; cin >> t; while (t--) {
        int a,b; cin >> a >> b;
        a = gcd(a, b);
        if (a == 1) {
            cout << "-1\n";
            continue;
        }
        int ans;
        for (ans = 2; ans*ans <= a && a % ans != 0; ans++);
        if (ans*ans > a) ans = a;
        cout << ans << "\n";
    }
}