← 返回题目列表

Codeforces · 1615/B

B. 并且它非零

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

给定一个数组,其中包含 $$$[l, r]$$$(含)中的所有整数。例如,如果 $$$l = 2$$$ 且 $$$r = 5$$$,则数组将为 $$$[2, 3, 4, 5]$$$。为了使数组的按位与非零,您可以删除的最小元素数量是多少?

按位 AND 是一种二进制运算,它采用两个等长的二进制表示形式,并对每对对应位执行 AND 运算。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。然后是 $$$t$$$ 案例。

每个测试用例的第一行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq 2 \cdot 10^5$$$) - 数组的描述。

输出

对于每个测试用例,输出一个整数 - 问题的答案。

示例

输入 #1

5
1 2
2 8
4 5
1 5
100000 200000

输出 #1

1
3
0
2
31072

注意

在第一个测试用例中,数组是 $$$[1, 2]$$$。目前,按位与为$$$0$$$,即$$$1\ \& \ 2 = 0$$$。然而,删除$$$1$$$(或$$$2$$$)后,数组变为$$$[2]$$$(或$$$[1]$$$),按位AND变为$$$2$$$(或$$$1$$$)。这可以被证明是最优的,所以答案是$$$1$$$。

在第二个测试用例中,数组为 $$$[2, 3, 4, 5, 6, 7, 8]$$$。目前,按位 AND 为 $$$0$$$。然而,删除$$$4$$$、$$$5$$$和$$$8$$$后,数组变为$$$[2,3,6,7]$$$,按位AND变为$$$2$$$。这可以被证明是最优的,所以答案是$$$3$$$。请注意,可能还有其他方法可以删除 $$$3$$$ 元素。