Binary Queries

Tired of carrying boxes from Giannis's warehouse back to his own, Takis sat down at his desk to try to come up with a problem for Phase ~A~ of the Greek Olympiad in Informatics (PDP). While experimenting on paper, he noticed that ~5~ ~AND~ ~4 = 4~, where ~AND~ is the bitwise operation ~AND~ (see here for its definition). He found this very interesting and wanted to know how often the bitwise ~AND~ of two numbers is equal to one of them.

Specifically, he has ~Q~ queries of the form ~(L,\;R)~, where ~L~ and ~R~ are non-negative integers and ~L \le R~. The answer to such a query is the number of pairs ~(x,\;y)~ such that ~L \le x \le R~ and ~L \le y \le R~, for which the following holds:

~x\;AND\;y = x~

Answer Takis's queries while he looks for interesting problems for Phase ~B~ as well.

Problem

Write a program in C++ that reads the input data from the file bqueries.in and prints the results to the file bqueries.out.

Input Files (bqueries.in)

The first line contains an integer ~Q~: the number of Takis's queries. The next ~Q~ lines each contain two integers ~L_i~ and ~R_i~: the ~i~-th query.

Output Files (bqueries.out)

The output must consist of ~Q~ lines, each containing an integer: the answer to the ~i~-th query.

Sample Input - Output Files:

Input:

2
3 7
777777 888888

Output:

11
75497532

Explanation:

For the first query, the ~11~ pairs of integers from ~3~ to ~7~ inclusive that satisfy the requirement are: ~(3,\;3)~, ~(3,\;7)~, ~(4,\;4)~, ~(4,\;5)~, ~(4,\;6)~, ~(4,\;7)~, ~(5,\;5)~, ~(5,\;7)~, ~(6,\;6)~, ~(6,\;7)~ and ~(7,\;7)~.

Constraints

• ~1 \le Q \le 200.000~
• ~0 \le L_i \le R_i \le 10^9~

Subtasks:

1. (13 points) ~L_i = 0~, ~R_i \le 5000~, for every ~i~ (where ~1 \le i \le Q~).
2. (16 points) ~L_i = 0~, ~R_i \le 200.000~, for every ~i~ (where ~1 \le i \le Q~).
3. (21 points) For every ~i~ (where ~1 \le i \le Q~), there exist positive integers ~k~, ~m~ such that ~L_i = 2^k~ and ~R_i = 2^m - 1~.
4. (27 points) ~L_i = 0~, for every ~i~ (where ~1 \le i \le Q~).
5. (23 points) There are no further constraints.

Notes:

• Formatting: In both the input and the output, each line ends with a newline character.
• Maximum execution time: ~2~ sec.
• Maximum available memory: ~64~ MB.

Warning: The answer may exceed ~2^{32}~ and, in general, you may need to perform operations with numbers larger than those that can be represented by the basic int type. Also, make sure to read the input and print the output efficiently in problems that require it.