#include <bits/stdc++.h>
using namespace std;
int root(int arr[], int i) {
  while (arr[i] != i) {
    arr[i] = arr[arr[i]];
    i = arr[i];
  }
  return i;
}
void Union(int arr[], int Size[], int a, int b) {
  int rootA = root(arr, a);
  int rootB = root(arr, b);
  if (Size[rootA] < Size[rootB]) {
    arr[rootA] = arr[rootB];
    Size[rootB] += Size[rootA];
  } else {
    arr[rootB] = arr[rootA];
    Size[rootA] += Size[rootB];
  }
}
bool findRoot(int a, int b, int arr[]) {
  if (root(arr, a) == root(arr, b))
    return true;
  else
    return false;
}
vector<vector<int> > adj(105);
bool nCyc = false;
int vis[55][55];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
long long solve(int i, int prev, int c) { return 0; }
int freq[200005], check[100005];
int main() {
  int t;
  cin >> t;
  while (t--) {
    int a, b;
    cin >> a >> b;
    if (b >= a)
      cout << 1 << endl;
    else if (b == 1)
      cout << a << endl;
    else {
      int ans = a;
      for (int i = 1; i * i <= a; i++) {
        if (a % i == 0 && i <= b) {
          ans = min(ans, a / i);
        }
        if (a / i <= b && a % i == 0) ans = min(ans, i);
      }
      cout << ans << endl;
    }
  }
  return 0;
}
