#include<stdio.h>
#include<math.h>
int c[1000001],a,b,n,nr,d[8][1000001];
void ciur(int n)
{
    c[2]=1;
    for (int i=4 ; i<=n ; i+=2)
        c[i]=1;
    int lim=(int)sqrt((double) n);
    for (int i=3 ; i<=n ; i+=2)
        if(c[i] == 0)
        {
            c[i]=1;
            for (int j=i*2 ; j<=n ; j+=i)
                if(j <= n)
                    ++c[j];
        }
}
int main()
{
    freopen("divprim.in" , "r" , stdin);
    freopen("divprim.out" , "w" , stdout);
    scanf("%d" , &a);
    ciur(1000000);
    for (int j=1 ; j<=7 ; ++j)
        for (int i=1 ; i<=1000000 ; ++i)
            if(c[i] == j)
                d[j][i]=i;
            else
                d[j][i]=d[j][i-1];
    a=1;
    while(scanf("%d %d" , &b , &n) != EOF)
    {
        if(n > 7)
        {
            printf("0\n");
            continue;
        }
        printf("%d\n" , d[n][b]-d[n][a-1]);
    }
    return 0;
}