#include <stdio.h>
#define MAX 1000000
long long primes[MAX+1];
char used[MAX+1];
int main()
{
int t,k,temp;
long long l,r,i,j,co;
for(i=2;i*i<=MAX;i++)
if(!primes[i])
for(j=i*i;j<=MAX;j+=i)
primes[j]=1;
for(j=0,i=2;i<=MAX;i++)
if(!primes[i])
primes[j++]=i;
primes[j]=((long long)MAX+1);
while(t--)
{
if(l==1)
co=1;
else
co=0;
for(i=0;i<=r-l;i++)
used[i]=0;
for(i=0;primes[i]*primes[i]<=r;i++)
for(j=primes[i]*primes[i];j<=r;j+=primes[i])
if(j>=l && !used[j-l])
{
co++;
used[j-l]=1;
}
co=r-l+1-co;
for(i=0;primes[i]*primes[i]<=r;i++)
for(temp=2,k=1,j=primes[i]*primes[i];j<=r;j*=primes[i],temp++)
{
if(j>=l && temp == primes[k]-1)
{
co++;
k++;
}
}
}
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNkZWZpbmUgTUFYIDEwMDAwMDAKbG9uZyBsb25nIHByaW1lc1tNQVgrMV07CmNoYXIgdXNlZFtNQVgrMV07CmludCBtYWluKCkKewogICAgaW50IHQsayx0ZW1wOwogICAgbG9uZyBsb25nIGwscixpLGosY287CiAKICAgIGZvcihpPTI7aSppPD1NQVg7aSsrKQogICAgIGlmKCFwcmltZXNbaV0pCiAgICAgICBmb3Ioaj1pKmk7ajw9TUFYO2orPWkpCiAgICAgICAgcHJpbWVzW2pdPTE7CiAKICAgIGZvcihqPTAsaT0yO2k8PU1BWDtpKyspCiAgICAgIGlmKCFwcmltZXNbaV0pCiAgICAgICAgcHJpbWVzW2orK109aTsKIAogICAgcHJpbWVzW2pdPSgobG9uZyBsb25nKU1BWCsxKTsKICAgIHNjYW5mKCIlZCIsJnQpOwogICAgd2hpbGUodC0tKQogICAgewogICAgICAgIHNjYW5mKCIlbGxkJWxsZCIsJmwsJnIpOwogCiAgICAgICAgaWYobD09MSkKICAgICAgICAgIGNvPTE7CiAgICAgICAgZWxzZQogICAgICAgICAgY289MDsKIAogICAgICAgIGZvcihpPTA7aTw9ci1sO2krKykKICAgICAgICAgIHVzZWRbaV09MDsKIAogICAgICAgIGZvcihpPTA7cHJpbWVzW2ldKnByaW1lc1tpXTw9cjtpKyspCiAgICAgICAgICAgZm9yKGo9cHJpbWVzW2ldKnByaW1lc1tpXTtqPD1yO2orPXByaW1lc1tpXSkKICAgICAgICAgICAgaWYoaj49bCAmJiAhdXNlZFtqLWxdKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgY28rKzsKICAgICAgICAgICAgICB1c2VkW2otbF09MTsKICAgICAgICAgICAgfQogICAgICAgIGNvPXItbCsxLWNvOwogCiAgICAgICAgZm9yKGk9MDtwcmltZXNbaV0qcHJpbWVzW2ldPD1yO2krKykKICAgICAgICAgICBmb3IodGVtcD0yLGs9MSxqPXByaW1lc1tpXSpwcmltZXNbaV07ajw9cjtqKj1wcmltZXNbaV0sdGVtcCsrKQogICAgICAgICAgIHsKICAgICAgICAgICAgIGlmKGo+PWwgJiYgdGVtcCA9PSBwcmltZXNba10tMSkKICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgY28rKzsKICAgICAgICAgICAgICAgaysrOwogICAgICAgICAgICAgfQogICAgICAgICAgIH0KIAogICAgICAgcHJpbnRmKCIlbGxkXG4iLGNvKTsKICAgIH0KICAgIHJldHVybiAwOwp9