#include <bits/stdc++.h>
using namespace std;
const int mx = 1e5 + 10;
const double PI = cos(-1.0);
int t, a[mx], n, m;
int main() {
  cin >> t;
  while (t--) {
    cin >> n >> m;
    int x = 0;
    for (int i = 1; i <= sqrt(n + 0.5); i++) {
      if (n % i == 0) {
        a[x++] = i;
        a[x++] = n / i;
      }
    }
    if (x == 2) {
      if (m >= n)
        cout << 1 << endl;
      else
        cout << n << endl;
    } else {
      int ans = 2e9 + 10;
      for (int i = 0; i < x; i++) {
        if (m >= a[i]) ans = min(ans, n / a[i]);
      }
      cout << ans << endl;
    }
  }
  return 0;
}
