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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while(T--){
        int N,K; cin >> N >> K;
        auto f = [&](int x) -> bool {
            for(int i=1; i*i<=x; i++) if(x%i == 0){
                int a = i,b = x/i;
                if(max(a,b) <= K) return false;
            }
            return true;
        };
        for(int i=N; i>=K; i--){
            if(i == K){cout << -1 << "\n"; break;}
            if(f(i)){cout << i << "\n"; break;}
        }
    }
}