#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int mod = 1e9 + 7, mod1 = 998244353, mod2 = 1e9 + 9, inf = 1e9 + 7;
long long infll = 1e18 + 7;
int n, m, k;
int ans, cnt, tmp, idx, sum, mx = -inf, mn = inf;
int x, y, z;
string s, t;
int a[N], b[N];
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int q = 1;
  cin >> q;
  while (q--) {
    cin >> n >> k;
    mx = -inf;
    for (int i = 1; i * i <= n; i++) {
      if (n % i == 0) {
        if (i <= k) {
          mx = max(mx, i);
        }
        if (n / i <= k) {
          mx = max(mx, n / i);
        }
      }
    }
    cout << n / mx << '\n';
  }
}
