#include using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--){ int n, k; cin >> n >> k; // n -> k + 1までの素数 // k * k + 1以上の合成数 if(n > (ll)(k) * k){ cout << n << '\n'; continue; } int ans = -1; while(n > k){ bool flg = true; for(int i = 1; i * i <= n; i++){ if(n % i == 0){ if(n / i <= k){ flg = false; break; } } } if(flg){ ans = n; break; } n--; } cout << ans << '\n'; } }