#include <bits/stdc++.h>
using namespace std;
using namespace chrono;
int SetBit(int n, int x) { return n | (1 << x); }
int ClearBit(int n, int x) { return n & ~(1 << x); }
int ToggleBit(int n, int x) { return n ^ (1 << x); }
bool CheckBit(int n, int x) { return (bool)(n & (1 << x)); }
int dx8[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dy8[] = {0, 1, 1, 1, 0, -1, -1, -1};
int dx4[] = {1, 0, -1, 0};
int dy4[] = {0, 1, 0, -1};
int __gcd(int a, int b) {
  if (a + b == 0) return a + b;
  if (a % b == 0) return b;
  return __gcd(b, a % b);
}
long long fact(int n) {
  long long res = 1;
  for (int i = 2; i <= n; i++) {
    res = res * i;
  }
  return res;
}
long long nCr(int n, int r) { return fact(n) / (fact(r) * fact(n - r)); }
long long nPr(int n, int r) { return fact(n) / fact(n - r); }
class myComp {
 public:
  bool operator()(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
  }
};
void solve() {
  int n, k;
  cin >> n >> k;
  int ans = 0;
  vector<int> v;
  for (int i = 1; i * i <= n; i++) {
    if (n % i) {
      continue;
    } else {
      if (n / i > k) {
        if (i <= k) v.push_back(n / i);
      } else {
        ans = i;
        break;
      }
    }
  }
  if (ans == 0) {
    cout << v[v.size() - 1] << "\n";
    ;
  } else
    cout << ans << "\n";
  ;
  return;
}
int32_t main() {
  int t;
  cin >> t;
  while (t--) solve();
  return 0;
}
