CF1245F.Daniel and Spring Cleaning

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.

丹尼尔在春季大扫除时，发现了一台他非常喜爱的老式计算器。然而，这台计算器似乎坏了：当他用它计算 $1 + 3$ 时，得到的结果是 $2$，而不是正确的 $4$；但当他计算 $1 + 4$ 时，却得到了正确答案 $5$。为解开这个谜团，他拆开了计算器，终于找到了原因：原本的全加器（full adders） 全部变成了半加器（half adders）！

因此，当他用这台计算器计算和 $a + b$ 时，实际得到的是异或和（xorsum） $a \oplus b$（异或运算的定义参见：https://en.wikipedia.org/wiki/Exclusive_or）。

正如他之前所观察到的，这台计算器有时仍会给出正确结果。于是他开始思考：给定整数 $l$ 和 $r$，有多少对整数 $(a, b)$ 满足以下条件？

$$a + b = a \oplus b$$

$$l \leq a \leq r$$

$$l \leq b \leq r$$

然而，酒保丹尼尔马上要去酒吧，两小时后才会回来。他要求你在他回来之前解决这个问题，否则你就得“享受”被封禁的待遇了。

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$).

第一行包含一个整数 $t$（$1 \le t \le 100$）—— 表示测试用例的数量。

接下来有 $t$ 行，每行包含两个以空格分隔的整数 $l$ 和 $r$（$0 \le l \le r \le 10^9$）。

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

输出 $t$ 个整数，其中第 $i$ 个整数应为第 $i$ 个测试用例的答案。

$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)$.

$a \oplus b$ 表示 $a$ 与 $b$ 的按位异或（XOR）运算。

对于第一个测试用例，满足条件的数对为：$(1, 2)$、$(1, 4)$、$(2, 1)$、$(2, 4)$、$(3, 4)$、$(4, 1)$、$(4, 2)$ 和 $(4, 3)$。