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
praveen123: 2014-01-20 01:59:26

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

Mitch Schwartz: 2014-01-20 01:59:26

This is very similar to some other problems on SPOJ, but I think it's ok to keep in classical for speed comparison as the constraints are higher.

Last edit: 2014-01-12 18:00:14

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