SPOJ.com - Problem SPCO

SPCO - Gopu and Counting Bitwise Prime Numbers

no tags

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⁵)

For next T lines, each test case contains two space separated integers a and b. (a ≤ b). 1 ≤ a, b ≤ 10¹⁹.

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

Submit solution!

hide comments

< Previous 1 2 3 Next >

	FooBar: 2014-01-20 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. Please be considerate towards non C/Java folks. I believe increasing time limit to 2~3 seconds still won't cause naive code to pass but might scuttle out Python to AC territory. --> (Reply by praveen123): I have updated the time limit to 3 secs. Though your solution times out still. Last edit: 2014-01-20 02:04:24
	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. :)

Submit solution!

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