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 seperated 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
hacker_sk:
20170617 01:31:20
dp and precomputation, 13th rank :) 

a_thinker:
20160625 20:33:42
@[Laksman] i getting TLE for the second test case,can u please elaborate a little what type of precomputation is nedded ? 

dwij28:
20160116 17:16:33
What is maximum value of ab in the test cases ? Is memorization possible ? 

shikhar jindal:
20150827 23:42:27
anyone plzz provide me with some test cases...i feel like my code is perfect but still getting wa..:(


shikhar jindal:
20150827 23:40:38
a and b,both are inclusive?


[Lakshman]:
20141208 09:07:12
@Pawankumar P Nothing special but precomputation makes it faster. 

Akash Agrawall:
20140722 09:53:21
@praveen123 nice question :) 

paras meena:
20140701 12:38:01
Change Input In Binary Then its simple Dp :D 

Aayush Agarwal:
20140621 16:44:58
Nice one ! 

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.

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 