#include <bits/stdc++.h>
namespace io {
template <typename T>
inline void read(T& _x) {
  int f = 0, ch;
  _x = 0;
  while (!isdigit(ch = getchar())) f |= ch == '-';
  while (isdigit(ch)) _x = _x * 10 + ch - '0', ch = getchar();
  if (f) _x = -_x;
}
template <typename T, typename... Args>
inline void read(T& _f, Args&... args) {
  read(_f), read(args...);
}
inline void _deal(char ch) { putchar(ch); }
template <typename T>
inline void _deal(T _x) {
  if (_x < 0) putchar('-'), _x = -_x;
  if (_x > 9) _deal(_x / 10);
  putchar(_x % 10 + '0');
}
inline void write() {}
template <typename T, typename... Args>
inline void write(T _f, Args... args) {
  _deal(_f), write(args...);
}
}  // namespace io
using namespace io;
int t, n, k;
int main() {
  read(t);
  while (t--) {
    read(n, k);
    int ans = 0x3f3f3f3f;
    for (int i = 1; i <= n / i; ++i)
      if (n % i == 0) {
        if (i <= k) ans = std::min(ans, n / i);
        if (n / i <= k) ans = std::min(ans, i);
      }
    write(ans, '\n');
  }
  return 0;
}
