#include<stdio.h>
#include<math.h>
int isPrimefast(unsigned long long int x);
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;
unsigned long long int i,p;
int j;
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];
unsigned long long int primes[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(i=0;i<m-n+1;++i)
primes[i] = 0;
for(p=2;p*p<=m;++p)
{
unsigned long long int less = n / p;
less *= p;
// first number <= N && p divides N
for(j=less;j<=m;j+=p)
{
if(j != p && j >= n)
primes[j - n] = 1;
}
}
for(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 0;
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;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8bWF0aC5oPgppbnQgaXNQcmltZWZhc3QodW5zaWduZWQgbG9uZyBsb25nIGludCB4KTsKIAppbnQgbWFpbigpIAp7IAppbnQgY2FzZW47IApzY2FuZigiJWRcbiIsICZjYXNlbik7IAp3aGlsZShjYXNlbi0tKSAKewogCiAKdW5zaWduZWQgbG9uZyBsb25nICBpbnQgbixtLGNvdW50LGNvdW50MSxqaixrayxpaSxkZCxmYWN0LGp1c3QxLGp1c3QyOwp1bnNpZ25lZCBsb25nIGxvbmcgaW50IGkscDsKaW50IGo7CmNvdW50PTAsY291bnQxPTA7IApzY2FuZigiJWxsZCAlbGxkXG4iLCZuLCZtKTsKanVzdDE9bjsKanVzdDI9bTsKLy9jb3VudD1jb3VudCtpc3NxdWFyZShuLG0pOwovL3ByaW50Zigibm8gb2Ygc3F1YXJlcy0tLS0tLT4lbGx1XG4iLGlzc3F1YXJlKG4sbSkpOwovL3Vuc2lnbmVkIGxvbmcgbG9uZyBpbnQgKiBwcmltZXMgPSBuZXcgdW5zaWduZWQgbG9uZyBsb25nIGludFttLW4rMV07IAp1bnNpZ25lZCBsb25nIGxvbmcgaW50IHByaW1lc1ttLW4rMV07Ci8vaW5pdGlhbGlzaW5nCmpqPXNxcnQoanVzdDEpOwovL3ByaW50ZigiVmFsdWUgb2YgamotLS0+ICVsbHVcbiIsamopOwpraz1zcXJ0KGp1c3QyKTsKLy9wcmludGYoImpqLS0tLT4lbGx1IGtrLS0tLT4lbGx1IGNvdW50MSAtLS0tLS0+JWxsdVxuIixqaixrayxjb3VudDEpOwppZihqaipqaiE9anVzdDEpCnsKamo9amorMTsKLy9wcmludGYoIkkgZGlkIGVudGVyXG4iKTsKfQovL3ByaW50ZigiVmFsdWUgb2YgamotLS0+ICVsbHVcbiIsamopOwpmb3IoaWk9amo7aWk8a2srMTtpaSsrKQp7ICAgZmFjdD0wOwoJZm9yKGRkPTE7ZGQ8aWk7ZGQrKykKCXsKCWlmKChpaSppaSklZGQ9PTApCgl7CgkvL3ByaW50ZigiVGhpcyBxdWFsaWZpZWQgYXMgYSBubyAlbGx1XG4iKTsKCWZhY3QrKzsKICAgIH0KICAgIH0KCWlmKGlzUHJpbWVmYXN0KChmYWN0KjIpKzEpPT0xKQoJewoJLy9wcmludGYoIkZhY3RvcnMgb2YgdGhlIG5vIGlzICVsbHVcdCAiLChmYWN0KjIpKzEpOwoJLy9wcmludGYoIlRoaXMgbm8gcXVhbGlmaWVzICVsbHVcbiIsaWkqaWkpOwoJY291bnQxKys7CiAgICB9CiAKfQogCi8vcHJpbnRmKCJDb3VudDEtLS0tPiAlbGx1XG4iLGNvdW50MSk7Ci8vcHJpbnRmKCJjb3VudCBub3cgJWxsdVxuIixjb3VudCk7CmZvcihpPTA7aTxtLW4rMTsrK2kpIApwcmltZXNbaV0gPSAwOyAKZm9yKHA9MjtwKnA8PW07KytwKSAKeyAKdW5zaWduZWQgbG9uZyBsb25nIGludCBsZXNzID0gbiAvIHA7CiBsZXNzICo9IHA7IAogLy8gZmlyc3QgbnVtYmVyIDw9IE4gJiYgcCBkaXZpZGVzIE4gCiBmb3Ioaj1sZXNzO2o8PW07ais9cCkgCiB7CiAKICAgIGlmKGogIT0gcCAmJiBqID49IG4pIAogICAgcHJpbWVzW2ogLSBuXSA9IDE7IAogfQogfSAKIGZvcihpPTA7aTxtLW4rMTsrK2kpIAogeyAKIGlmKHByaW1lc1tpXSA9PSAwICYmIG4raSAhPSAxKQogeyAgCiAgIAljb3VudCsrOwogICAJLy9wcmludGYoImNvdW50IHZhbHVlIGluY3JlYXNlZCB0byAlbGx1Iixjb3VudCk7CiB9IAogCiAvLyBXZSBkb24ndCB3YW50IHRvIHByaW50IGlmIGl0J3MgMSAKIC8vcHJpbnRmKCIlbGxkXG4iLG4raSk7IAogfQogLy9jb3VudD1jb3VudCtjb3VudDE7CiBwcmludGYoIiVsbHUiLGNvdW50K2NvdW50MSk7IAogaWYoY2FzZW4pIAogcHJpbnRmKCJcbiIpOyAKIC8vZGVsZXRlIFtdIHByaW1lczsgCiB9CiByZXR1cm4gMDsgCiB9IAppbnQgaXNQcmltZWZhc3QodW5zaWduZWQgbG9uZyBsb25nIGludCB4KQp7ICAgCgkgbG9uZyBsb25nIGludCBrLGo7CglrPXNxcnQoeCk7CgkvL3ByaW50Zigiay0tLS0tPiVsbGRcbiIsayk7CgkKCWlmKHg9PTEpCglyZXR1cm4gMDsKCWlmKHg9PTIpCglyZXR1cm4gMTsKCWlmKHg9PTMpCglyZXR1cm4gMTsKCWlmKHg9PTQpCglyZXR1cm4gMDsKCWlmKHg9PTUpCglyZXR1cm4gMTsKCQoJaWYoKHgtMSklNj09MHx8KHgrMSklNj09MHx8eCUyIT0wfHx4JTMhPTB8fHglNSE9MHx8eCU3IT0wKQoJewoJCglmb3Ioaj0yO2o8aysxO2orKykKCXsgICAKCQogICAgICAJCgkJaWYoeCVqPT0wKQoJCXJldHVybiAwOwoJCQoJfQoJcmV0dXJuIDE7CiAgICB9CiAgICBlbHNlCiAgICByZXR1cm4gMDsKfQ==