#include<set>
#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
const int N=500005;

int prime[N],p;
bool iscomp[N+1];

void primetable()
{
    for(int i=2;i<=N;i++)
    {
        if(iscomp[i]==false) prime[p++]=i;
        for(int j=0;j<p&&i*prime[j]<=N;j++)
        {
            iscomp[i*prime[j]]=true;
            if(i%prime[j]==0) break;
        }
    }
}

int main()
{
    primetable();
    int T;
    scanf("%d", &T);
    int ss=0;
    while (T--)
    {
        long long n,d;
        scanf("%I64d%I64d",&n,&d);
        int ans=0;
        int i;
        long long tp;
        int flag=0;
        for(i=0;i<p;i++)
        {
            tp=d*prime[i];
            if(tp>=n) break;
            ans++;
            if(d%prime[i]==0) break;
            if(prime[i]*prime[i]>d) {flag=1;break;}
        }
        if(flag==0)
        {
            printf("%d\n",ans);
        }
        else
        {
            int l=0,r=p-1;
            while(l<r)
            {
                int mid=(l+r+1)/2;
                tp=d*prime[mid];
                if(prime[mid]>d||tp>=n) r=mid-1;
                else l=mid;
            }
            printf("%d\n",l+1);
        }
    }
    return 0;
}