#include <bits/stdc++.h>
using namespace std;
int main() {
  int t;
  cin >> t;
  while (t) {
    int n, k;
    cin >> n >> k;
    if (n <= k)
      cout << "1\n";
    else {
      int korobok = n, c = 2;
      while (c * c <= n)
        if (n % c == 0) {
          if (c <= k) korobok = min(korobok, n / c);
          if (n / c <= k) korobok = min(korobok, c);
          c++;
        } else
          c++;
      cout << korobok << endl;
    }
    t--;
  }
  return 0;
}
