#include <bits/stdc++.h>
using namespace std;
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long cnt = 0;
    for (long long i = 1; i <= min(k, static_cast<long long>(sqrt(n))); i++) {
      if (n % i == 0 && n / i <= k) {
        cout << i;
        break;
      } else if (n % i == 0) {
        cnt = n / i;
      }
      if (i == min(k, static_cast<long long>(sqrt(n)))) {
        cout << cnt;
      }
    }
    cout << "\n";
  }
  return 0;
}
