package Basic;
import java.util.Arrays;
import java.util.Scanner;
public class Prime_Number {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int tc = scan.nextInt();
// if(Basic_Prime(num)) {
// System.out.println(“Prime”);
// }else {
// System.out.println(“Not Prime”);
// }
// Print_Primes(num);
while(tc>0) {
int n = scan.nextInt();
int n1 = scan.nextInt();
Prime_Bitcount(n,n1);
tc–;
}
}
private static void Prime_Bitcount(int s,int e) {
int P_count=0;
for(int i=s;i<=e;i++) {
int prime = Find_Binary(i);
if(isPrime(prime)) {
P_count++;
}
System.out.println(P_count);
}
}
private static int Find_Binary(int num) {
int binary =0;
int mul = 1;
int count=0;
while(num!=0) {
int rem =num%2;
// System.out.println("rem "+rem);
binary = binary+(mulrem);
mul = mul10;
num = num/2;
}
count = Bit_Count(binary);
return count;
}
static boolean isPrime(int n)
{
// Corner cases
if (n <= 1) return false;
if (n <= 3) return true;
// This is checked so that we can skip
// middle five numbers in below loop
if (n%2 == 0 || n%3 == 0) return false;
for (int i=5; i*i<=n; i=i+6)
if (n%i == 0 || n%(i+2) == 0)
return false;
return true;
}
private static int Bit_Count(int binary) {
int count =0;
while(binary!=0) {
int rem = binary%10;
if(rem==1) {
count++;
}
binary = binary/10;
}
return count;
}
}