#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
bool isp[32005];
int p[32005],cnt=0;
void init()
{
    memset(isp,1,sizeof(isp));
    int i,j,t;
    for(i=2;i<=32000;++i)
    {
        if(isp[i])
            p[++cnt]=i;
        for(j=1;j<=cnt;++j)
        {
            if((t=p[j]*i)>32000)
                break;
            isp[t]=0;
            if(!(i%p[j]))
                break;
        }
    }
}
int main()
{
    init();
    int i,ans,T,n,d;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&d);
        ans=0;
        for(i=1;i<=cnt;++i)
        {
            if(p[i]*d>=n)
                break;
            ++ans;
            if(!(d%p[i]))
                break;
        }
        printf("%d\n",ans);
    }
    return 0;
}