给定一个数组,其中包含 $$$[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$$$ 元素。