#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;
sieve();
while(t-->0){
ulong l,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++;
}
}
}
}
I2luY2x1ZGU8c3RkaW8uaD4KLy8jaW5jbHVkZTxtYXRoLmg+CiNkZWZpbmUgdHJ1ZSAxCiNkZWZpbmUgZmFsc2UgMAp0eXBlZGVmIHVuc2lnbmVkIGxvbmcgbG9uZyB1bG9uZzsKaW50IHByaW1lWzEwMDAwMDBdOwogCiAKdWxvbmcgcG93ZXIodWxvbmcgYSxpbnQgbil7CmlmKG49PTApCnJldHVybiAxOwppZihuJjEpewp1bG9uZyBwPXBvd2VyKGEsbj4+MSk7CnJldHVybiBhKnAqcDsKfQplbHNlCnsKdWxvbmcgcD1wb3dlcihhLG4+PjEpOwpyZXR1cm4gcCpwOwp9Cn0KIAppbnQgcmV0dXJuSW5kZXgoaW50IGksdWxvbmcgbCl7CmlmKGk+bCkKcmV0dXJuIDI7CmludCBqOwpmb3Ioaj0yO2o8MTAwO2orKyl7CmlmKCFwcmltZVtqLTFdKXsKaWYocG93ZXIoaSxqLTEpPj1sKQp7CnJldHVybiBqOwp9Cn0KfQp9CnZvaWQgc2lldmUoKXsKaW50IGk7CmZvcihpPTI7aTw9MTAwMDtpKyspewppbnQgcD0xLTElaTsKaWYoaSppPnApCnA9aSppOwppZihwPT1pIHx8IHA8MSkKcCs9aTsKd2hpbGUocDw9MTAwMDAwMCl7CnByaW1lW3AtMV09dHJ1ZTsKcCs9aTsKfQp9Cn0KaW50IG1haW4oKXsKaW50IHQ7CnNjYW5mKCIlZCIsJnQpOwpzaWV2ZSgpOwp3aGlsZSh0LS0+MCl7CnVsb25nIGwscjsKc2NhbmYoIiVsbHUiLCZsKTsKc2NhbmYoIiVsbHUiLCZyKTsKaW50IHNpemU9ci1sKzE7CmludCBpbnB1dFtzaXplXTsKLy8gcHJpbnRmKCJIZXJlIEkgQW1cbiIpOwovLyBwcmludGYoIkhlcmUgSSBBbVxuIik7CmludCBpLGo7CmZvcihpPTA7aTxzaXplO2krKykKaW5wdXRbaV09MTsKLy9tYXJrIGFsbCBwcmltZSBwb3dlcnMgb2YgcHJpbWVzLi4uCmZvcihpPTI7aTw9ciAmJiBpPDEwMDAwMDA7aSsrKXsKaWYoIXByaW1lW2ktMV0pewppbnQgcmVtID0gbCVpOwppbnQgaW5kZXg9MDsKaWYocmVtIT0wKQppbmRleCA9IGktcmVtOwpmb3Ioaj1pbmRleDtqPHNpemU7ais9aSl7CmlmKChqK2wpPT1pKQp7aW5wdXRbal09MTsKLy9wcmludGYoImFwcGx5aW5nIDEgb24gaj0lbGx1IGZvciBpPSVkXG4iLGorbCxpKTsKfQplbHNlewkKLy8gcHJpbnRmKCJ1bm1hcmtpbmcgJWxsdSBmb3IgaT0lZFxuIixqK2wsaSk7CmlucHV0W2pdPTA7Cn0KfQp9Cn0KLy9wcmludGYoInByaW1lIHBvd2VycyBzdWNjZXNzZnVsbHkgZG9uZS5cbiIpOwovLyBmb3IoaT0wO2k8c2l6ZTtpKyspCi8vIHByaW50ZigibWFyaz0lZCBpPSVkIHZhbHVlPSVsbHVcbiIsaW5wdXRbaV0saSxpK2wpOwpmb3IoaT0yO2k8PXIgJiYgaTwxMDAwMDAwO2krKyl7CmlmKCFwcmltZVtpLTFdKXsKaW50IHJldCA9IHJldHVybkluZGV4KGksbCk7CmZvcihqPXJldDtqPjA7aisrKXsKaWYoIXByaW1lW2otMV0pewp1bG9uZyB0ZW1wPXBvd2VyKGksai0xKTsKaWYodGVtcD5yKXsKYnJlYWs7Cn0KZWxzZXsKaW5wdXRbdGVtcC1sXT0xOwovL3ByaW50ZigibWFya2luZyBpdCBiYWNrICVsbHUgZm9yIGk9JWRcbiIsdGVtcCxpKTsKfQkKfQp9Cn0KfQkKaW50IGNvdW50PTA7CmlmKGw9PTEpCmlucHV0WzBdPTA7CmZvcihpPTA7aTxzaXplO2krKyl7CmlmKGlucHV0W2ldKXsKLy9wcmludGYoIiVsbHVcbiIsaStsKTsKY291bnQrKzsKfQp9CnByaW50ZigiJWRcbiIsY291bnQpOwp9Cn0=