#include <cstdio>

#include <cmath>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <queue>

#include <vector>

#include <map>



using namespace std;



typedef long long LL;


bool f[10000005];
int g[10000005];
int s[10000005];
int num;
int p[10000005];
int T,n,d,ans,a,b;

int main()

{
    memset(f,true,sizeof(f));
    for (int i=2;i<=10000000;++i)
    {
        if (f[i]==false) continue;
        g[i]=i;
        ++num;p[num]=i;
        for (int j=i+i;j<=10000000;j+=i)
        {
            if (f[j]==true) g[j]=i;
            f[j]=false;
        }
    }
    f[1]=false;
    g[1]=0;
    s[0]=0;
    for (int i=1;i<=10000000;++i)
    {
        if (f[i]) s[i]=s[i-1]+1;
        else s[i]=s[i-1];
    }
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&d);
        if (d<=10000000)
        {
            a=(n-1)/d;
            b=g[d];
        }
        else
        {
            a=(n-1)/d;
            b=10000;
            for (int i=1;i<=num;++i)
            {
                if (p[i]>a) break;
                if (d%p[i]==0)
                {
                    b=p[i];
                    break;
                }
            }
        }
        if (a<b) ans=s[a];
        else ans=s[b];
        printf("%d\n",ans);
    }

    return 0;

}