#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<time.h>
#include<assert.h>
#include<iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int>pi;
const int Maxn=100020;
int isp[Maxn],g[Maxn];
vector<int>pri;
void getp(){
    for(int i=2;i<Maxn;i++){
        if(!isp[i])pri.push_back(i),g[i]=i;
        for(int j=0;j<pri.size();j++){
            int x=pri[j];
            if(x*i>=Maxn)break;
            isp[x*i]=1;
            if(i%x==0){g[x*i]=g[i];break;}
            else g[x*i]=x;
        }
    }
    for(int i=2;i<Maxn;i++){
        if(!isp[i])isp[i]=isp[i-1]+1;
        else isp[i]=isp[i-1];
    }
}
int main(){
    getp();
    int _;scanf("%d",&_);
    int n,d;
    while(_--){
        scanf("%d%d",&n,&d);
        n--;
        int tmp=n/d;
        if(d<Maxn)tmp=min(tmp,g[d]);
        else{
            for(int i=0;i<pri.size()&&pri[i]<=tmp&&1LL*pri[i]*pri[i]<=d;i++){
                if(d%pri[i]==0){
                    tmp=min(tmp,pri[i]);
                    break;
                }
            }
        }
        //printf("tmp=%d\n",tmp);
        printf("%d\n",isp[tmp]);    
    }
    return 0;
}