#include <bits/stdc++.h>
using namespace std;
inline int read() {
  char ch = getchar();
  int f = 1, x = 0;
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}
int t;
int n, k;
int main() {
  t = read();
  while (t--) {
    n = read();
    k = read();
    int ans = n;
    for (int i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        if (n / i <= k) ans = min(ans, i);
        if (i <= k) ans = min(ans, n / i);
      }
    }
    cout << ans << "\n";
  }
  return 0;
}
