#include <bits/stdc++.h>
using namespace std;
long long a[100005];
int32_t main() {
  long long t, n, k;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    long long ans = n, i;
    for (i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        long long x = i, y = n / i;
        if (x <= k) ans = min(ans, n / x);
        if (y <= k) ans = min(ans, n / y);
      }
    }
    cout << ans << "\n";
  }
}
