#include <bits/stdc++.h>
using namespace std;
template <class c>
struct rge {
  c b, e;
};
template <class c>
rge<c> range(c i, c j) {
  return rge<c>{i, j};
}
template <class c>
auto dud(c* x) -> decltype(cerr << *x, 0);
template <class c>
char dud(...);
struct debug {
  template <class c>
  debug& operator<<(const c&) {
    return *this;
  }
};
long long int power(long long int x, long long int y,
                    long long int mod = 1000000007) {
  long long int ret = 1;
  x = x % mod;
  while (y) {
    if (y & 1) ret = (ret * x) % mod;
    y = y >> 1;
    x = (x * x) % mod;
  }
  return ret % mod;
}
long long int isprime(long long int x) {
  for (long long int i = 2; i * i <= x; i++)
    if (x % i == 0) return 0;
  return 1;
}
void solve() {
  long long int n, k;
  cin >> n >> k;
  if (n <= k) {
    cout << 1 << endl;
    return;
  }
  vector<long long int> fact;
  for (long long int i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      if (i <= k) fact.push_back(i);
      if ((n / i) <= k) fact.push_back(n / i);
    }
  }
  sort(fact.begin(), fact.end());
  cout << n / fact.back() << endl;
}
signed main() {
  long long int t;
  cin >> t;
  while (t--) solve();
}
