#include <iostream>
#include <math.h>
#include <stdio.h>
using namespace std;
typedef long long uint64;
int prime(uint64 n)
{
uint64 i=2;
int flag=0;
while(i<=sqrt(n))
{
if(n%i==0)
{
flag=1;
break;
}
i++;
}
if(flag==0)
return 1;
}
uint64 prime1(uint64 l,uint64 r)
{
uint64 i,j,z=0,*primes;
//primes = malloc(sizeof(int)*limit);
primes= new (nothrow) uint64[r];
for (i=2;i<r;i++)
primes[i]=1;
for (i=2;i<r;i++)
if (primes[i])
for (j=i;i*j<r;j++)
primes[i*j]=0;
for (i=l;i<r;i++)
if (primes[i])
z++;
return z;
}
int main()
{
int t,k;
uint64 i,l,r;
scanf("%d",&t);
for(k=0;k<t;k++)
{
scanf("%lld %lld",&l,&r);
long count=0;
if(l==1)
{
l++;
}
if(r==1)
{
r--;
cout<<count;
break;
}
count+=prime1(l,r);
for(i=l;i<=r;i++)
{
double a=sqrt(i);
if(a==floor(a))
{
uint64 j=1,c=1;
while(j<a)
{
if(i%j==0)
{
c=c+2;
}
j++;
}
if(prime(c)==1)
{
count++;
}
}
}
cout<<count<<"\n";
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8c3RkaW8uaD4KIAp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCnR5cGVkZWYgbG9uZyBsb25nIHVpbnQ2NDsgCiAKaW50IHByaW1lKHVpbnQ2NCBuKQp7CiAgICB1aW50NjQgaT0yOwogICAgaW50IGZsYWc9MDsKICAgIHdoaWxlKGk8PXNxcnQobikpCiAgICB7CiAgICAgICAgaWYobiVpPT0wKQogICAgICAgIHsKICAgICAgICAgICAgZmxhZz0xOwogICAgICAgICAgICBicmVhazsKICAgICAgICB9CiAgICAgICAgaSsrOwogICAgfQogICAgaWYoZmxhZz09MCkKICAgICAgICByZXR1cm4gMTsKfQogCnVpbnQ2NCBwcmltZTEodWludDY0IGwsdWludDY0IHIpCnsKICAgIHVpbnQ2NCBpLGosej0wLCpwcmltZXM7CiAKICAgIC8vcHJpbWVzID0gbWFsbG9jKHNpemVvZihpbnQpKmxpbWl0KTsKICAgIHByaW1lcz0gbmV3IChub3Rocm93KSB1aW50NjRbcl07CiAgICBmb3IgKGk9MjtpPHI7aSsrKQogICAgICAgIHByaW1lc1tpXT0xOwogCiAgICBmb3IgKGk9MjtpPHI7aSsrKQogICAgICAgIGlmIChwcmltZXNbaV0pCiAgICAgICAgICAgIGZvciAoaj1pO2kqajxyO2orKykKICAgICAgICAgICAgICAgIHByaW1lc1tpKmpdPTA7CiAKICAgIGZvciAoaT1sO2k8cjtpKyspCiAgICAgICAgaWYgKHByaW1lc1tpXSkKICAgICAgICAgICAgeisrOwogICAKICAgcmV0dXJuIHo7Cn0KIAppbnQgbWFpbigpCnsKICAgIGludCB0LGs7CiAgICB1aW50NjQgaSxsLHI7CiAgICBzY2FuZigiJWQiLCZ0KTsgICAgCiAgICBmb3Ioaz0wO2s8dDtrKyspCiAgICB7CiAgICAgICAgc2NhbmYoIiVsbGQgJWxsZCIsJmwsJnIpOwogICAgICAgIGxvbmcgY291bnQ9MDsKICAgICAgICBpZihsPT0xKQogICAgICAgIHsKICAgICAgICAgICAgbCsrOwogICAgICAgIH0KICAgICAgICBpZihyPT0xKQogICAgICAgIHsKICAgICAgICAgICAgci0tOwogICAgICAgICAgICBjb3V0PDxjb3VudDsKICAgICAgICAgICAgYnJlYWs7CiAgICAgICAgfQogICAgICAgIGNvdW50Kz1wcmltZTEobCxyKTsKICAgICAgICBmb3IoaT1sO2k8PXI7aSsrKQogICAgICAgIHsKICAgICAgICAgICAgZG91YmxlIGE9c3FydChpKTsKICAgICAgICAgICAgCiAgICAgICAgICAgIGlmKGE9PWZsb29yKGEpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICB1aW50NjQgaj0xLGM9MTsKICAgICAgICAgICAgICAgIHdoaWxlKGo8YSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZihpJWo9PTApCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIAljPWMrMjsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgaisrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgaWYocHJpbWUoYyk9PTEpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICBjb3V0PDxjb3VudDw8IlxuIjsKICAgIH0KICAgcmV0dXJuIDA7Cn0g