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^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

hide comments
sharansh12: 2018-08-19 09:40:29

for c++ use unsigned long long

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 !


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