#include #define ll long long #define ull unsigned long long #define dl double #define st first #define nd second #define II pair using namespace std; const int N = 5 + 1e5; const int inf = 7 + 1e9; void solve() { int n, k; cin >> n >> k; if (n == k) { cout << "-1\n"; return; } ll spr = (ll)k * k; if (spr < n) { cout << n << '\n'; return; } while (n > 0) { int ok = 1; for (int i = 1; i * i <= n, i <= k; i ++) if (n % i == 0) { int x = n / i; if (x <= k) { ok = 0; break; } } if (ok) { cout << n << '\n'; return; } n --; } cout << "-1\n"; } int main() { #define TASKNAME "" 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; cin >> t; while (t --) solve(); return 0; }