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
hacker_sk: 2017-06-17 01:31:20

dp and precomputation, 13th rank :)

a_thinker: 2016-06-25 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: 2016-01-16 17:16:33

What is maximum value of a-b in the test cases ? Is memorization possible ?

shikhar jindal: 2015-08-27 23:42:27

anyone plzz provide me with some test cases...i feel like my code is perfect but still getting wa..:(
a very silly mistake...finally accepted..:)

Last edit: 2015-08-28 00:37:36
shikhar jindal: 2015-08-27 23:40:38

a and b,both are inclusive?

[Lakshman]: 2014-12-08 09:07:12

@Pawankumar P Nothing special but pre-computation makes it faster.

Akash Agrawall: 2014-07-22 09:53:21

@praveen123 nice question :)

paras meena: 2014-07-01 12:38:01

Change Input In Binary Then its simple Dp :D

Aayush Agarwal: 2014-06-21 16:44:58

Nice one !

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

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