#include <bits/stdc++.h>
using namespace std;
int main() {
  long long n, t, i, k, ans, x;
  scanf("%lld", &t);
  while (t--) {
    scanf("%lld", &n), scanf("%lld", &k);
    if (n <= k)
      ans = 1;
    else {
      i = sqrt(n);
      i = min(i, k);
      ans = INT_MAX;
      for (; i >= 1; i--) {
        if (n % i == 0) {
          x = n / i;
          if (x <= k)
            ans = min(ans, min(i, x));
          else
            ans = min(ans, x);
        }
      }
    }
    printf("%lld ", ans);
    printf("\n");
  }
  return 0;
}
