#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("avx,avx2,fma")
using namespace std;
const string alpha = "abcdefghijklmnopqrstuvwxyz";
const long long N = 1e9;
long long binexp(long long a, long long b, long long m) {
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % m;
    a = a * a % m;
    b >>= 1;
  }
  return res;
}
void task(bool flag) {
  if (flag)
    cout << "YES\n";
  else
    cout << "NO\n";
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long T = 0;
  cin >> T;
  while (T--) {
    long long n, k;
    cin >> n >> k;
    long long ans = n;
    for (long long i = 1; i <= sqrt(n); ++i) {
      if (n % i == 0) {
        if (i * i == n) {
          if (i <= k) {
            ans = min(ans, i);
          }
        } else {
          if (n / i <= k) {
            ans = min(ans, i);
          }
          if (i <= k) {
            ans = min(ans, n / i);
          }
        }
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
