#include<iostream>
#include<stdlib.h>
#include<math.h>
#include<map>
#include<algorithm>
#define N 101000
#define LOOK cout<<"sadg\n"
using namespace std;

int p[N],sum[N];
bool prime[N];
void init(){
    for(int i=2;i<N;++i)
        prime[i]=1;
    for(int i=2;i<N;++i){
        if(prime[i])
            p[++p[0]]=i,sum[i]=1;
        for(int j=1;j<=p[0] && i*p[j]<N;j++)
            prime[i*p[j]]=0;
    }
    for(int i=1;i<N;++i)
        sum[i]+=sum[i-1];
}

map<int,int >hs;

int main(){
    init();
    int T;scanf("%d",&T);
    while(T--){
        int n,d;
        scanf("%d%d",&n,&d);
        int uplim=min((n-1)/d,d),temp=d,div;
        if(!(div=hs[d])){
            for(int i=1;p[i]*p[i]<=d;++i)
                if(d%p[i]==0){
                    temp=p[i];
                    break;
                }
            div=hs[d]=temp;
        }
        uplim=min(uplim,div);
        printf("%d\n",sum[uplim]);
//        cout<<hs[d]<<endl;
    }
    return 0;
}
/*

*/