#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