← 返回题目列表

Codeforces · 1245/F

F. 丹尼尔和春季大扫除

中文机器翻译题面 查看原题

在进行春季大扫除时,丹尼尔发现了一个他非常喜欢的旧计算器。不过,好像已经坏掉了。当他尝试使用计算器计算 $$$1 + 3$$$ 时,他得到 $$$2$$$ 而不是 $$$4$$$。但当他尝试计算 $$$1 + 4$$$ 时,他得到了正确答案 $$$5$$$。对此谜团感到困惑的他打开计算器,找到了谜语的答案:全加器变成了半加器!

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

正如他之前看到的,计算器有时会给出正确的答案。因此,他想知道,给定整数 $$$l$$$ 和 $$$r$$$,有多少对整数 $$$(a, b)$$$ 满足以下条件: $$$$$$a + b = a \oplus b$$$$$ $$$$$l \leq a \leq r$$$$$$ $$$$$$l \leq b \leq r$$$$$$

然而,酒保丹尼尔要去酒吧,两小时后回来。他告诉你在他回来之前解决问题,否则你将不得不享受被封锁的乐趣。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

然后是 $$$t$$$ 行,每行包含两个空格分隔的整数 $$$l$$$ 和 $$$r$$$ ($$$0 \le l \le r \le 10^9$$$)。

输出

打印 $$$t$$$ 整数,第 $$$i$$$ 个整数应该是第 $$$i$$$ 个测试用例的答案。

示例

输入 #1

3
1 4
323 323
1 1000000

输出 #1

8
0
3439863766

注意

$$$a \oplus b$$$ 表示 $$$a$$$ 和 $$$b$$$ 的按位异或。

对于第一个测试用例,这些对是: $$$(1, 2)$$$、$$$(1, 4)$$$、$$$(2, 1)$$$、$$$(2, 4)$$$、$$$(3, 4)$$$、$$$(4, 1)$$$、$$$(4, 2)$$$ 和$$$(4, 3)$$$。