#include<stdio.h>
//#include<math.h>
#define true 1
#define false 0
typedef unsigned long long ulong;
int prime[1000000];
ulong power(ulong a,int n){
if(n==0)
return 1;
if(n&1){
ulong p=power(a,n>>1);
return a*p*p;
}
else
{
ulong p=power(a,n>>1);
return p*p;
}
}
int returnIndex(int i,ulong l){
if(i>l)
return 2;
int j;
for(j=2;j<100;j++){
if(!prime[j-1]){
if(power(i,j-1)>=l)
{
return j;
}
}
}
}
void sieve(){
int i;
for(i=2;i<=1000;i++){
int p=1-1%i;
if(i*i>p)
p=i*i;
if(p==i || p<1)
p+=i;
while(p<=1000000){
prime[p-1]=true;
p+=i;
}
}
}
int main(){
int t;
scanf("%d",&t);
sieve();
while(t-->0){
ulong l,r;
scanf("%llu",&l);
scanf("%llu",&r);
int size=r-l+1;
int input[size];
// printf("Here I Am\n");
// printf("Here I Am\n");
int i,j;
for(i=0;i<size;i++)
input[i]=1;
//mark all prime powers of primes...
for(i=2;i<=r && i<1000000;i++){
if(!prime[i-1]){
int rem = l%i;
int index=0;
if(rem!=0)
index = i-rem;
for(j=index;j<size;j+=i){
if((j+l)==i)
{input[j]=1;
//printf("applying 1 on j=%llu for i=%d\n",j+l,i);
}
else{
// printf("unmarking %llu for i=%d\n",j+l,i);
input[j]=0;
}
}
}
}
//printf("prime powers successfully done.\n");
// for(i=0;i<size;i++)
// printf("mark=%d i=%d value=%llu\n",input[i],i,i+l);
for(i=2;i<=r && i<1000000;i++){
if(!prime[i-1]){
int ret = returnIndex(i,l);
for(j=ret;j>0;j++){
if(!prime[j-1]){
ulong temp=power(i,j-1);
if(temp>r){
break;
}
else{
input[temp-l]=1;
//printf("marking it back %llu for i=%d\n",temp,i);
}
}
}
}
}
int count=0;
if(l==1)
input[0]=0;
for(i=0;i<size;i++){
if(input[i]){
//printf("%llu\n",i+l);
count++;
}
}
printf("%d\n",count);
}
}
I2luY2x1ZGU8c3RkaW8uaD4KLy8jaW5jbHVkZTxtYXRoLmg+CiNkZWZpbmUgdHJ1ZSAxCiNkZWZpbmUgZmFsc2UgMAp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bG9uZzsKaW50IHByaW1lWzEwMDAwMDBdOwogCiAKdWxvbmcgcG93ZXIodWxvbmcgYSxpbnQgbil7CglpZihuPT0wKQoJcmV0dXJuIDE7CglpZihuJjEpewoJCXVsb25nIHA9cG93ZXIoYSxuPj4xKTsKCQlyZXR1cm4gYSpwKnA7CgkJfQoJZWxzZSAKCXsKCQl1bG9uZyBwPXBvd2VyKGEsbj4+MSk7CgkJcmV0dXJuIHAqcDsKCQl9Cn0KIAppbnQgcmV0dXJuSW5kZXgoaW50IGksdWxvbmcgbCl7CglpZihpPmwpCglyZXR1cm4gMjsKCWludCBqOwoJZm9yKGo9MjtqPDEwMDtqKyspewoJCWlmKCFwcmltZVtqLTFdKXsKCQkJaWYocG93ZXIoaSxqLTEpPj1sKQoJCQl7CgkJCXJldHVybiBqOwoJCQl9CgkJfQoJfQp9CnZvaWQgc2lldmUoKXsKCQlpbnQgaTsKCQlmb3IoaT0yO2k8PTEwMDA7aSsrKXsKCQlpbnQgcD0xLTElaTsKCQlpZihpKmk+cCkKCQlwPWkqaTsKCQkKCQlpZihwPT1pIHx8IHA8MSkKCQlwKz1pOwoJCQoJCXdoaWxlKHA8PTEwMDAwMDApewoJCQlwcmltZVtwLTFdPXRydWU7CgkJCXArPWk7CgkJfQoJfQp9CmludCBtYWluKCl7CglpbnQgdDsKCXNjYW5mKCIlZCIsJnQpOwkJCglzaWV2ZSgpOwp3aGlsZSh0LS0+MCl7Cgl1bG9uZyBsLHI7CglzY2FuZigiJWxsdSIsJmwpOwkKCXNjYW5mKCIlbGx1Iiwmcik7CglpbnQgc2l6ZT1yLWwrMTsKaW50IGlucHV0W3NpemVdOwovLwlwcmludGYoIkhlcmUgSSBBbVxuIik7CQkKLy8JcHJpbnRmKCJIZXJlIEkgQW1cbiIpOwoJaW50IGksajsKCWZvcihpPTA7aTxzaXplO2krKykKCWlucHV0W2ldPTE7CQoJLy9tYXJrIGFsbCBwcmltZSBwb3dlcnMgb2YgcHJpbWVzLi4uCglmb3IoaT0yO2k8PXIgJiYgaTwxMDAwMDAwO2krKyl7CgkJaWYoIXByaW1lW2ktMV0pewoJCQlpbnQgcmVtID0gbCVpOwoJCQlpbnQgaW5kZXg9MDsKCQkJaWYocmVtIT0wKQoJCQlpbmRleCA9IGktcmVtOwoJCQlmb3Ioaj1pbmRleDtqPHNpemU7ais9aSl7CgkJCQlpZigoaitsKT09aSkKCQkJCXtpbnB1dFtqXT0xOwovL3ByaW50ZigiYXBwbHlpbmcgMSBvbiBqPSVsbHUgZm9yIGk9JWRcbiIsaitsLGkpOwp9CgkJCQllbHNlewkKLy8JcHJpbnRmKCJ1bm1hcmtpbmcgJWxsdSBmb3IgaT0lZFxuIixqK2wsaSk7CgkJCQlpbnB1dFtqXT0wOwoJCQkJfQoJCQl9CgkJfQoJfQoJLy9wcmludGYoInByaW1lIHBvd2VycyBzdWNjZXNzZnVsbHkgZG9uZS5cbiIpOwovLwlmb3IoaT0wO2k8c2l6ZTtpKyspCi8vCXByaW50ZigibWFyaz0lZCBpPSVkIHZhbHVlPSVsbHVcbiIsaW5wdXRbaV0saSxpK2wpOwkKCWZvcihpPTI7aTw9ciAmJiBpPDEwMDAwMDA7aSsrKXsKCQlpZighcHJpbWVbaS0xXSl7CgkJCWludCByZXQgPSByZXR1cm5JbmRleChpLGwpOwoJCWZvcihqPXJldDtqPjA7aisrKXsKCQkJaWYoIXByaW1lW2otMV0pewoJCQl1bG9uZyB0ZW1wPXBvd2VyKGksai0xKTsKCQkJCWlmKHRlbXA+cil7CgkJCQlicmVhazsKCQkJCX0KCQkJCWVsc2V7CgkJCQlpbnB1dFt0ZW1wLWxdPTE7Ci8vcHJpbnRmKCJtYXJraW5nIGl0IGJhY2sgJWxsdSBmb3IgaT0lZFxuIix0ZW1wLGkpOwp9CQkJCn0KCQl9CgkJfQoJfQkKCWludCBjb3VudD0wOwoJaWYobD09MSkKCWlucHV0WzBdPTA7CgkKCWZvcihpPTA7aTxzaXplO2krKyl7CgkJaWYoaW5wdXRbaV0pewoJLy9wcmludGYoIiVsbHVcbiIsaStsKTsJCgkJY291bnQrKzsKCQl9Cgl9CglwcmludGYoIiVkXG4iLGNvdW50KTsJCn0KfQ==
NTAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAwCjEgMTAwMDAwMAo5OTk5OTkwMDAwMDAgMTAwMDAwMDAwMDAwMAoxIDEwMDAwMDAKOTk5OTk5MDAwMDAwIDEwMDAwMDAwMDAwMDAKMSAxMDAwMDAwCjk5OTk5OTAwMDAwMCAxMDAwMDAwMDAwMDAw
50
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000
1 1000000
999999000000 1000000000000