#include <bits/stdc++.h>
using namespace std;
vector<long long int> fac;
void printDivisors(int n) {
  for (int i = 1; i <= sqrt(n); i++) {
    if (n % i == 0) {
      if (n / i == i) {
        fac.emplace_back(i);
      } else {
        fac.emplace_back(i);
        fac.emplace_back(n / i);
      }
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    if (k >= n)
      cout << "1"
           << "\n";
    else {
      fac.clear();
      printDivisors(n);
      sort(fac.begin(), fac.end(), greater<long long int>());
      for (long long int i = 0; i < fac.size(); i++) {
        if (fac[i] <= k) {
          cout << n / fac[i] << "\n";
          break;
        }
      }
    }
  }
  return 0;
}
