adssd

#include <iostream>
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
#include <cmath>

using namespace std;
set<long long> bruh;

int main() {
    long long t,i,n,k,j;
    scanf("%lld",&t);
    for(i=0;i<t;i++) {
        bruh.clear();
        scanf("%lld %lld",&n,&k);
        if(k >= n) {
            printf("1\n");
        } else {
            for(j=1;j*j<=n;j++) {
                if(n%j == 0 && n/j <= k) {
                    printf("%lld\n",j);
                    bruh.insert(j);
                    break;
                }
            }
            if(bruh.size() == 0) {
                printf("%lld\n",n);
            }
        }
    }
    return 0;
}