#include<stdio.h>
const long maxn=1000007;
long n,k,b[maxn][8],a[maxn],i,t,j;
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    b[1][0]=0;
    for(i=2;i<maxn;i++)
    {
        if(!a[i])
            for(j=i;j<maxn;j+=i)
                ++a[j];
        for(j=0;j<=7;j++)
            b[i][j]=b[i-1][j];
        if(a[i]<=7)
            b[i][a[i]];
    }
    scanf("%ld",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%ld %ld",&n,&k);
        printf("%ld\n",b[n][k]);
    }
    return 0;
}