#include using namespace std; #define int long long #define db double #define gcd(a,b) __gcd(a,b) #define lcm(a,b) a*b / __gcd(a,b) #define I first #define II second #define pb push_back #define ii pair const int INF = 2 * 1e18; const int N = 3e5 + 1; const int MOD = 1e9 + 7; int n, k; int ok(int n) { for (int i = 2; i * i <= n && i <= k; i++) if (n % i == 0 && i <= k && n / i <= k) return 0; return 1; } void solve() { cin >> n >> k; for (int i = n; i > k; i--) if (ok(i)) { cout << i << '\n'; return ; } cout << -1 << '\n'; } int32_t main() { #define TASKNAME "test" ios_base::sync_with_stdio(0); cin.tie(0); if (fopen(TASKNAME ".inp","r" )) { freopen(TASKNAME ".inp","r",stdin); freopen(TASKNAME ".out","w",stdout); } int t = 1; cin >> t; while (t--) solve(); return 0; }