Daniel and Spring Cleaning
Contest: Codeforces Round 597 (Div. 2)
Difficulty rating: 2300
Tags: bitmasks, brute force, combinatorics, dp

While doing some spring cleaning, Daniel found an old calculator that he loves so much. However, it seems like it is broken. When he tries to compute $$$1 + 3$$$ using the calculator, he gets $$$2$$$ instead of $$$4$$$. But when he tries computing $$$1 + 4$$$, he gets the correct answer, $$$5$$$. Puzzled by this mystery, he opened up his calculator and found the answer to the riddle: the full adders became half adders!

So, when he tries to compute the sum $$$a + b$$$ using the calculator, he instead gets the xorsum $$$a \oplus b$$$ (read the definition by the link: https://en.wikipedia.org/wiki/Exclusive_or).

As he saw earlier, the calculator sometimes gives the correct answer. And so, he wonders, given integers $$$l$$$ and $$$r$$$, how many pairs of integers $$$(a, b)$$$ satisfy the following conditions: $$$$$$a + b = a \oplus b$$$$$$ $$$$$$l \leq a \leq r$$$$$$ $$$$$$l \leq b \leq r$$$$$$

However, Daniel the Barman is going to the bar and will return in two hours. He tells you to solve the problem before he returns, or else you will have to enjoy being blocked.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of testcases.

Then, $$$t$$$ lines follow, each containing two space-separated integers $$$l$$$ and $$$r$$$ ($$$0 \le l \le r \le 10^9$$$).

Output format:
Print $$$t$$$ integers, the $$$i$$$-th integer should be the answer to the $$$i$$$-th testcase.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
$$$a \oplus b$$$ denotes the bitwise XOR of $$$a$$$ and $$$b$$$.

For the first testcase, the pairs are: $$$(1, 2)$$$, $$$(1, 4)$$$, $$$(2, 1)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(4, 1)$$$, $$$(4, 2)$$$, and $$$(4, 3)$$$.

Example input:
3
1 4
323 323
1 1000000

Example output:
8
0
3439863766

Editorial:
Claim. Let $$$x$$$, $$$y$$$ be nonnegative integers. If $$$x + y = x \oplus y$$$, then $$$x * y = 0$$$, where $$$x * y$$$ is the bitwise AND of $$$x$$$ and $$$y$$$.
Proof. Recall that bitwise XOR is just addition in base two without carry. So if addition is to be equal to addition in base two without carry, then there must be no carry when added in base two, which is what we wanted.
Define a function $$$f$$$ as follows: let $$$l$$$ and $$$r$$$ be nonnegative integers, then $$$f(l, r)$$$ should be the number of pairs of integers $$$(x, y)$$$ such that the following conditions are satisfied:
• $$$l \leq x < r$$$
• $$$l \leq y < r$$$
• $$$x + y = x \oplus y$$$
Notice that $$$f(0, r) = 2r - 1 + f(1, r)$$$.
Claim. Let $$$l$$$ and $$$r$$$ be positive integers. Then, $$$f(2l, 2r) = 3 \cdot f(l, r)$$$.
Proof. Let $$$x$$$, $$$y$$$ be positive integers. Suppose we want the following conditions to be satisfied:
• $$$2l \leq x < 2r$$$
• $$$2l \leq y < 2r$$$
• $$$x + y = x \oplus y$$$
What if $$$l$$$ and $$$r$$$ are not both even? Define a function $$$g$$$ as follows: let $$$x$$$ and $$$n$$$ be nonnegative integers, then $$$g(x, n)$$$ should be the number of integers $$$y$$$ such that the following conditions are satisfied:
• $$$0 \leq y < n$$$
• $$$x + y = x \oplus y$$$
Now all that remains is to implement $$$g$$$ efficiently. Define a function $$$\textrm{LSB}$$$ as follows: let $$$n$$$ be a positive integer, then $$$\textrm{LSB}(n)$$$ should be the least significant 1-bit of $$$n$$$. Next, define a function $$$h$$$ as follows: let $$$x$$$ and $$$n$$$ be positive integers, then $$$h(x, n)$$$ should be the number of integers $$$y$$$ such that the following conditions are satisfied:
• $$$n - \textrm{LSB}(n) \leq y < n$$$
• $$$x + y = x \oplus y$$$