SPCO  Gopu and Counting Bitwise Prime Numbers
A positive integer is said to be bitwise prime if the sum of all the bits in its binary representation is a prime number.
You are given two integers a and b. You have to output number of bitwise prime numbers between a and b (inclusive).
Input
First line contains T : number of test cases. (1 <= T <= 10^5)
For next T lines, each test case contains two space separated integers a and b. (a <= b). 1 <= a, b <= 10^19.
Output
For each test case, print the number of bitwise prime numbers between a and b (inclusive).
Example
Input: 2
1 2
1 3 Output: 0
1
hide comments
FooBar:
20140120 01:59:26
Time limit is crazy for interpreted languages like Python. After all sorts of optimizations, my Python code times out. But *exactly* same code translated into C++ passes in < 0.4 seconds.


RISHABH JAIN:
20140120 01:59:26
nice problem


[Lakshman]:
20140120 01:59:26
Thanks for providing the test cases, I have two solution but second one is wrong, With first one I am getting correct answer for all cases which was provided by abdou. But still WA. 

Mitch Schwartz:
20140120 01:59:26
Don't ask for spoilers. From your encouragement, another user posted a bunch of cases and their answers (that comment is now hidden, I guess by the problem setter). Moreover, you can check 1 to 100 easily by brute force! 

[Lakshman]:
20140120 01:59:26
@All who got Ac Please help me what is answer for 1 100. 

abdou_93:
20140120 01:59:26
@Lakshman ... i think there is case like


[Lakshman]:
20140120 01:59:26
what is the max difference between a and b? 

anurag garg:
20140120 01:59:26
TLE....


Mitch Schwartz:
20140120 01:59:26
@praveen123: Fast I/O for me only saved 0.05s, so I don't know why you chose to single out that detail, but thanks for the info. :) 
Added by:  praveen123 
Date:  20131223 
Time limit:  3s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  IITK ACA CSE online judge 