#include <bits/stdc++.h>
using namespace std;
int main() {
  long long int t;
  cin >> t;
  while (t--) {
    long long int n, k;
    cin >> n >> k;
    long long int arr[1000009];
    long long int p = 0;
    if (n <= k)
      printf("1\n");
    else {
      for (long long int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
          if (n / i == i) {
            arr[p] = i;
            p++;
          } else {
            arr[p] = i;
            p++;
            arr[p] = n / i;
            p++;
          }
        }
      }
      sort(arr, arr + p);
      for (long long int i = p - 1; i >= 0; i--) {
        if (arr[i] <= k) {
          printf("%lld\n", n / arr[i]);
          break;
        }
      }
    }
  }
}
