SPCO - Gopu and Counting Bitwise Prime Numbers

no tags 

 

A positive integer is said to be Bit-sum-prime if the sum of all the bits in
its binary representation is a prime number

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

hide comments
RISHABH JAIN: 2014-01-20 01:59:26

nice problem

[Lakshman]: 2014-01-20 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: 2014-01-20 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]: 2014-01-20 01:59:26

@All who got Ac Please help me what is answer for 1 100.

abdou_93: 2014-01-20 01:59:26

@Lakshman ... i think there is case like
1 10000000000000000000

Last edit: 2014-01-13 22:54:05
[Lakshman]: 2014-01-20 01:59:26

what is the max difference between a and b?

anurag garg: 2014-01-20 01:59:26

TLE....
any better way to count set bits..?

Last edit: 2014-01-12 23:57:10
Mitch Schwartz: 2014-01-20 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. :)

praveen123: 2014-01-20 01:59:26

@Mitch - your fastIO solution is slower then my solution :P


Added by:praveen123
Date:2013-12-23
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge