#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1000000;
int vis[maxn];
int prime[maxn];
void sieve(int n){
    memset(vis, 0, sizeof(vis));
    for(int i = 2; i * i <= n; i++) if(!vis[i])
        for(int j = i * i; j <= n; j += i) vis[j] = 1;
}
int get_primes(int n){
    sieve(n);
    int c = 0;
    for(int i = 2; i <= n; i++) if(!vis[i]) prime[++c] = i;
    return c;
}
int GetMin(int d, int t){
    for(int i = 1; prime[i] < t && prime[i] * prime[i] <= d; i++)
        if(d % prime[i] == 0) return prime[i];
    return min(d, t);
}        
int GetNum(int p, int n){
    int l = 0, r = n;
    while(r - l > 1){
        int m = l + (r - l) / 2;
        if(p > prime[m]) l = m;
        else if(p < prime[m]) r = m;
        else if(p == prime[m]) return m;
    }
    return l;
}
int main(){
    int c = get_primes(1000000);
    int T;
    scanf("%d", &T);
    for(int ca = 0; ca < T; ca++){
        int n, d;
        scanf("%d%d", &n, &d);
        int t = (n - 1) / d;
        int s = GetMin(d, t);
//        printf("t:%d s:%d\n", t, s);
        printf("%d\n", GetNum(min(t, s), c));
    }
    return 0;
}