#include using namespace std; #define rep(i, n) for (int i = 0; i < (n); ++i) using ll = long long; using ull = unsigned long long; inline bool f(const int x, const int k) { for (int i = 1; i * i <= x; ++i) { if (x % i == 0) { if (i <= k && x / i <= k) return false; } } return true; } inline void solve() { int n, k; cin >> n >> k; for (int i = n; i >= max(1, n - 281); --i) { if (f(i, k)) { cout << i << "\n"; return; } } cout << -1 << '\n'; } int main() { cin.tie(nullptr)->sync_with_stdio(false); int t; cin >> t; while (t--) solve(); return 0; }