#include <bits/stdc++.h>
using namespace std;
const double pi = acos(-1.0);
template <typename T, typename U>
inline void amin(T& x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
inline void amax(T& x, U y) {
  if (x < y) x = y;
}
template <typename T>
inline void write(T x) {
  int i = 20;
  char buf[21];
  buf[20] = '\n';
  do {
    buf[--i] = x % 10 + '0';
    x /= 10;
  } while (x);
  do {
    putchar(buf[i]);
  } while (buf[i++] != '\n');
}
template <typename T>
inline T readInt() {
  T n = 0, s = 1;
  char p = getchar();
  if (p == '-') s = -1;
  while ((p < '0' || p > '9') && p != EOF && p != '-') p = getchar();
  if (p == '-') s = -1, p = getchar();
  while (p >= '0' && p <= '9') {
    n = (n << 3) + (n << 1) + (p - '0');
    p = getchar();
  }
  return n * s;
}
void print_test_case(int i) {
  string test_case = "Case #" + to_string(i) + ": ";
  cout << test_case;
}
void print_ln() { cout << '\n'; }
class Debugger {
 public:
  Debugger(const std::string& _separator = " - ")
      : first(true), separator(_separator) {}
  template <typename ObjectType>
  Debugger& operator,(const ObjectType& v) {
    if (!first)
    std:
      cerr << separator;
    std::cerr << v;
    first = false;
    return *this;
  }
  ~Debugger() {
  std:
    cerr << endl;
  }

 private:
  bool first;
  std::string separator;
};
vector<int> factors(int x) {
  vector<int> result;
  int i = 1;
  while (i * i <= x) {
    if (x % i == 0) {
      result.push_back(i);
      if (x / i != i) {
        result.push_back(x / i);
      }
    }
    i++;
  }
  return result;
}
void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> factors_arr = factors(n);
  sort(factors_arr.begin(), factors_arr.end());
  while (factors_arr.back() > k) {
    factors_arr.pop_back();
  }
  cout << n / factors_arr.back() << endl;
}
int main() {
  int tc;
  cin >> tc;
  while (tc > 0) {
    solve();
    tc--;
  }
  return 0;
}
