#include <bits/stdc++.h>
#define ll long long
#define int long long
#define double long double
#define float double
#define pb push_back
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define nl '\n'
#define here cout << "HERE" << endl;
#define forn(i, a, n) for (int i = a; i < n; i++)
#define print(a) for (auto& e : a) cout << e << " "; cout << endl;
#define MOD(a, b) (((a) % (b) + (b)) % (b))
#define yesno(b) cout << ((b) ? "YES\n" : "NO\n")
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using vi = vector<int>;
vi seive(int n){
    vector<bool> prime(n+1,true);
    for(int i=2;i*i<=n;i++){
        if(prime[i]==true){
            for(int j=i*i;j<=n;j+=i)prime[j]=false;
        }
    }
    vi res;
    for(int i=2;i<=n;i++){
        if(prime[i])res.pb(i);
    }
    return res;
}
vi primes=seive(1e6);
vi factorisation(int n,const vi &primes){
    vi factors;
    for(auto p:primes){
        if(p*p>n)break;
        while(n%p==0){
            factors.pb(p);
            n/=p;
        }
    }
    if(n>1)factors.pb(n);
    return factors;
}
vector<vector<int>> g;
vector<int> vis;
void bfs(int s){
    queue<int> q;
    q.push(s);
    vis[s] = 1;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int v : g[u]){
            if(!vis[v]){
                vis[v] = 1;
                q.push(v);
            }
        }
    }
}
void dfs(int u){
    vis[u] = 1;
    for(int v : g[u])
        if(!vis[v]) dfs(v);
}
void solve(){
    int n,k;
    cin>>n>>k;
    if(n==k){
        cout << -1 << nl;
        return;
    }else{
        for(int i=n;i>0;i--){
            vi arr=factorisation(i,primes);
            if(arr.back()>k){
                cout << i << nl;
                return;
            }
        }
    }
}

signed main(){
    fast
    int t = 1;
    cin >> t;
    while (t--) solve();
    return 0;
}