#include <bits/stdc++.h>
using namespace std;
int main() {
  long long t, n, i, j, k, a, b, c;
  cin >> t;
  while (t--) {
    long long ans = 0;
    cin >> n >> k;
    a = sqrt(n) + 1;
    long long maxi = 0;
    for (i = 1; i <= a; i++) {
      if (n % i == 0) {
        b = i;
        c = n / i;
      }
      if (c > maxi && k >= c) {
        maxi = c;
      } else if (b > maxi && k >= b) {
        maxi = b;
      }
    }
    ans = n / maxi;
    cout << ans << endl;
  }
}
