#include<stdio.h>
#include<math.h>
int isPrimefast(unsigned long long int x);
using namespace std;
int main()
{
int casen;
scanf("%d\n", &casen);
while(casen--)
{
unsigned long long int n,m,count,count1,jj,kk,ii,dd,fact,just1,just2;
count=0,count1=0;
scanf("%lld %lld\n",&n,&m);
just1=n;
just2=m;
//count=count+issquare(n,m);
//printf("no of squares------>%llu\n",issquare(n,m));
unsigned long long int * primes = new unsigned long long int[m-n+1];
//initialising
jj=sqrt(just1);
//printf("Value of jj---> %llu\n",jj);
kk=sqrt(just2);
//printf("jj---->%llu kk---->%llu count1 ------>%llu\n",jj,kk,count1);
if(jj*jj!=just1)
{
jj=jj+1;
//printf("I did enter\n");
}
//printf("Value of jj---> %llu\n",jj);
for(ii=jj;ii<kk+1;ii++)
{ fact=0;
for(dd=1;dd<ii;dd++)
{
if((ii*ii)%dd==0)
{
//printf("This qualified as a no %llu\n");
fact++;
}
}
if(isPrimefast((fact*2)+1)==1)
{
//printf("Factors of the no is %llu\t ",(fact*2)+1);
//printf("This no qualifies %llu\n",ii*ii);
count1++;
}
}
//printf("Count1----> %llu\n",count1);
//printf("count now %llu\n",count);
for(unsigned long long int i=0;i<m-n+1;++i)
primes[i] = 0;
for(unsigned long long int p=2;p*p<=m;++p)
{
unsigned long long int less = n / p;
less *= p;
// first number <= N && p divides N
for(int j=less;j<=m;j+=p)
{
if(j != p && j >= n)
primes[j - n] = 1;
}
}
for(unsigned long long int i=0;i<m-n+1;++i)
{
if(primes[i] == 0 && n+i != 1)
{
count++;
//printf("count value increased to %llu",count);
}
// We don't want to print if it's 1
//printf("%lld\n",n+i);
}
//count=count+count1;
printf("%llu",count+count1);
if(casen)
printf("\n");
//delete [] primes;
}
return 0;
}
int isPrimefast(unsigned long long int x)
{
long long int k,j;
k=sqrt(x);
//printf("k----->%lld\n",k);
if(x==1)
return 0;
if(x==2)
return 1;
if(x==3)
return 1;
if(x==4)
return false;
if(x==5)
return 1;
if((x-1)%6==0||(x+1)%6==0||x%2!=0||x%3!=0||x%5!=0||x%7!=0)
{
for(j=2;j<k+1;j++)
{
if(x%j==0)
return 0;
}
return 1;
}
else
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgppbnQgaXNQcmltZWZhc3QodW5zaWduZWQgbG9uZyBsb25nIGludCB4KTsKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IG1haW4oKSAKeyAKaW50IGNhc2VuOyAKc2NhbmYoIiVkXG4iLCAmY2FzZW4pOyAKd2hpbGUoY2FzZW4tLSkgCnsKCgp1bnNpZ25lZCBsb25nIGxvbmcgIGludCBuLG0sY291bnQsY291bnQxLGpqLGtrLGlpLGRkLGZhY3QsanVzdDEsanVzdDI7Cgpjb3VudD0wLGNvdW50MT0wOyAKc2NhbmYoIiVsbGQgJWxsZFxuIiwmbiwmbSk7Cmp1c3QxPW47Cmp1c3QyPW07Ci8vY291bnQ9Y291bnQraXNzcXVhcmUobixtKTsKLy9wcmludGYoIm5vIG9mIHNxdWFyZXMtLS0tLS0+JWxsdVxuIixpc3NxdWFyZShuLG0pKTsKdW5zaWduZWQgbG9uZyBsb25nIGludCAqIHByaW1lcyA9IG5ldyB1bnNpZ25lZCBsb25nIGxvbmcgaW50W20tbisxXTsgCi8vaW5pdGlhbGlzaW5nCmpqPXNxcnQoanVzdDEpOwovL3ByaW50ZigiVmFsdWUgb2YgamotLS0+ICVsbHVcbiIsamopOwpraz1zcXJ0KGp1c3QyKTsKLy9wcmludGYoImpqLS0tLT4lbGx1IGtrLS0tLT4lbGx1IGNvdW50MSAtLS0tLS0+JWxsdVxuIixqaixrayxjb3VudDEpOwppZihqaipqaiE9anVzdDEpCnsKamo9amorMTsKLy9wcmludGYoIkkgZGlkIGVudGVyXG4iKTsKfQovL3ByaW50ZigiVmFsdWUgb2YgamotLS0+ICVsbHVcbiIsamopOwpmb3IoaWk9amo7aWk8a2srMTtpaSsrKQp7ICAgZmFjdD0wOwoJZm9yKGRkPTE7ZGQ8aWk7ZGQrKykKCXsKCWlmKChpaSppaSklZGQ9PTApCgl7CgkvL3ByaW50ZigiVGhpcyBxdWFsaWZpZWQgYXMgYSBubyAlbGx1XG4iKTsKCWZhY3QrKzsKICAgIH0KICAgIH0KCWlmKGlzUHJpbWVmYXN0KChmYWN0KjIpKzEpPT0xKQoJewoJLy9wcmludGYoIkZhY3RvcnMgb2YgdGhlIG5vIGlzICVsbHVcdCAiLChmYWN0KjIpKzEpOwoJLy9wcmludGYoIlRoaXMgbm8gcXVhbGlmaWVzICVsbHVcbiIsaWkqaWkpOwoJY291bnQxKys7CiAgICB9Cgp9CgovL3ByaW50ZigiQ291bnQxLS0tLT4gJWxsdVxuIixjb3VudDEpOwovL3ByaW50ZigiY291bnQgbm93ICVsbHVcbiIsY291bnQpOwpmb3IodW5zaWduZWQgbG9uZyBsb25nIGludCBpPTA7aTxtLW4rMTsrK2kpIApwcmltZXNbaV0gPSAwOyAKZm9yKHVuc2lnbmVkIGxvbmcgbG9uZyBpbnQgcD0yO3AqcDw9bTsrK3ApIAp7IAp1bnNpZ25lZCBsb25nIGxvbmcgaW50IGxlc3MgPSBuIC8gcDsKIGxlc3MgKj0gcDsgCiAvLyBmaXJzdCBudW1iZXIgPD0gTiAmJiBwIGRpdmlkZXMgTiAKIGZvcihpbnQgaj1sZXNzO2o8PW07ais9cCkgCiB7CiAKICAgIGlmKGogIT0gcCAmJiBqID49IG4pIAogICAgcHJpbWVzW2ogLSBuXSA9IDE7IAogfQogfSAKIGZvcih1bnNpZ25lZCBsb25nIGxvbmcgaW50IGk9MDtpPG0tbisxOysraSkgCiB7IAogaWYocHJpbWVzW2ldID09IDAgJiYgbitpICE9IDEpCiB7ICAKICAgCWNvdW50Kys7CiAgIAkvL3ByaW50ZigiY291bnQgdmFsdWUgaW5jcmVhc2VkIHRvICVsbHUiLGNvdW50KTsKIH0gCiAKIC8vIFdlIGRvbid0IHdhbnQgdG8gcHJpbnQgaWYgaXQncyAxIAogLy9wcmludGYoIiVsbGRcbiIsbitpKTsgCiB9CiAvL2NvdW50PWNvdW50K2NvdW50MTsKIHByaW50ZigiJWxsdSIsY291bnQrY291bnQxKTsgCiBpZihjYXNlbikgCiBwcmludGYoIlxuIik7IAogLy9kZWxldGUgW10gcHJpbWVzOyAKIH0KIHJldHVybiAwOyAKIH0gCmludCBpc1ByaW1lZmFzdCh1bnNpZ25lZCBsb25nIGxvbmcgaW50IHgpCnsgICAKCSBsb25nIGxvbmcgaW50IGssajsKCWs9c3FydCh4KTsKCS8vcHJpbnRmKCJrLS0tLS0+JWxsZFxuIixrKTsKCQoJaWYoeD09MSkKCXJldHVybiAwOwoJaWYoeD09MikKCXJldHVybiAxOwoJaWYoeD09MykKCXJldHVybiAxOwoJaWYoeD09NCkKCXJldHVybiBmYWxzZTsKCWlmKHg9PTUpCglyZXR1cm4gMTsKCQoJaWYoKHgtMSklNj09MHx8KHgrMSklNj09MHx8eCUyIT0wfHx4JTMhPTB8fHglNSE9MHx8eCU3IT0wKQoJewoJCglmb3Ioaj0yO2o8aysxO2orKykKCXsgICAKCQogICAgICAJCgkJaWYoeCVqPT0wKQoJCXJldHVybiAwOwoJCQoJfQoJcmV0dXJuIDE7CiAgICB9CiAgICBlbHNlCiAgICByZXR1cm4gMDsKfQkKCQoJCgo=