#include <bits/stdc++.h>
using namespace std;
long long check(long long n, long long m) {
  long long i, j;
  set<long long> s;
  s.insert(1);
  for (i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) {
      s.insert(i);
      s.insert(n / i);
    }
  }
  auto itr = s.rbegin();
  long long ans;
  j = s.size();
  while (j > 0) {
    if (*itr <= m) {
      ans = *itr;
      break;
    } else {
      itr++;
      j--;
    }
  }
  return n / ans;
}
int main() {
  long long t, n, m, i, k, j;
  cin >> t;
  while (t--) {
    cin >> n >> m;
    k = n;
    if (n <= m)
      cout << 1 << endl;
    else {
      cout << check(n, m) << endl;
    }
  }
}
