#include <cstdio>
typedef long long LL;
const int N = 100000 + 5;
LL n, d;
bool prime[N];//prime[i]表示i是不是质数
int p[N], tot;//p[N]用来存质数
void init(){
    for(int i = 2; i < N; i ++) prime[i] = true;//初始化为质数
    for(int i = 2; i < N; i++){
        if(prime[i]) p[tot ++] = i;//把质数存起来
        for(int j = 0; j < tot && i * p[j] < N; j++){
            prime[i * p[j]] = false;
            if(i % p[j] == 0) break;//保证每个合数被它最小的质因数筛去
        }
    }
}
int solve(){
    int ret = 0;
    for(int i = 0; i < tot; i ++){
        if(d*p[i] >= n){
            return ret;
        }
        ret ++;
        if(d % p[i] == 0){
            return ret;
        }
    }
    return ret;
}
int main(){
    init();
    int T;
    scanf("%d", &T);
    while(T --){
        scanf("%I64d%I64d", &n, &d);
        if(n <= d){
            printf("0\n");
            continue;
        }
        printf("%d\n", solve());
    }
}