#include <bits/stdc++.h>
using namespace std;
void solve3() {
  int n;
  cin >> n;
  vector<int> v(n);
  int a = 0, b = 0;
  for (int &e : v) {
    cin >> e;
    if (e % 2 == 0)
      a++;
    else
      b++;
  }
  if (a % 2 != b % 2)
    cout << "NO" << endl;
  else {
    if (a % 2 == 0)
      cout << "YES" << endl;
    else {
      for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
          if (v[i] % 2 != v[j] % 2 && abs(v[i] - v[j]) == 1) {
            cout << "YES" << endl;
            return;
          }
        }
      }
      cout << "NO" << endl;
    }
  }
}
void solve4() {
  long long n, k;
  cin >> n >> k;
  long long ans = n;
  for (long long j = 1; j <= sqrt(n); j++) {
    if (n % j == 0) {
      if (j <= k) ans = min(ans, n / j);
      if (n / j <= k) ans = min(ans, j);
    }
  }
  cout << ans << endl;
}
int main() {
  int t;
  cin >> t;
  while (t--) {
    solve4();
  }
  return 0;
}
