#include using namespace std; #define rep(i,n) for(int i = 0; i < n; ++i) using ll = long long; int solve(void) { int N, K; cin >> N >> K; for(int x = N; x > K; --x) { bool flag = 1; for(int i = 2; i * i <= x and i <= K; ++i) { if(x % i == 0 and x / i <= K) { flag = 0; break; } } if(flag) { cout << x << endl; return 0; } } cout << -1 << endl; return 0; } int main(void) { int T; cin >> T; while(T--) solve(); return 0; }