#include <bits/stdc++.h>
using namespace std;
int main() {
  ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  ;
  int t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    set<long long> st;
    for (int i = 1; i <= sqrt(n); i++) {
      if (n % i == 0) {
        st.insert(i);
        st.insert(n / i);
      }
    }
    long long diff = INT_MAX;
    for (auto itr = st.begin(); itr != st.end(); itr++) {
      if (*itr <= k) {
        long long k = *itr;
        long long p = n / k;
        if (p < diff) diff = p;
      } else
        break;
    }
    cout << diff << endl;
  }
}
