#include <bits/stdc++.h>
using namespace std;
int main() {
  int tc, cse = 0;
  cin >> tc;
  while (tc--) {
    int a, b;
    cin >> a >> b;
    int sqt = sqrt(a);
    if (a <= b)
      cout << 1 << "\n";
    else {
      int ans;
      int times = a, tt = 0, get = 0;
      for (int i = 1; i < sqt + 1; i++) {
        if (a % i == 0) {
          if (i <= b) {
            times = min(times, a / i);
          }
          if (a / i <= b) {
            times = min(times, i);
          }
        }
      }
      cout << times << "\n";
    }
  }
}
