Sheldon and Periodic Numbers

0

0 votes
Medium
Problem

Sheldon is trying to solve a problem and even after applying nearly all of his knowledge, he is unable to solve it.

The problem states that you are given two integers L and R and you have to calculate the count of numbers which falls in range [L, R] and are periodic.

A number is said to be periodic if it's binary representation(without leading zeros) can be divided into X blocks such that--

  • 2Xlen and X is a divisor of len, where len is the length of binary representation(without leading zeros) of given number.

  • Each of the X blocks is identical to one another.

Your have to find the count of such numbers in range [L, R].

PS: The problem is actually very easy for Sheldon and above statement was just for the sake of problem "story" :P.

Input Format:

First line contains T, number of test cases.

Each of next T lines contains 2 integers L and R, denoting the given range.

Output Format:

For each test case, output the required answer in separate lines.

Constraints:

1T10

1L,R1018

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

For first case, 3, 7 and 10 are periodic in their binary representation which is 11, 111 and 1010 receptively. Partitioning is 1|1, 1|1|1 and 10|10.

For second case, 31 and 36 are periodic in their binary representation which is 11111 and 100100 respectively. Partitioning is 1|1|1|1|1 and 100|100.

Editor Image

?