← 返回题目列表

Codeforces · 1632/C

C. 奇怪的测试

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

Igor 正在上 11 年级。明天他必须参加学校最严格的老师帕维尔·杰尼索维奇的信息学考试。

Igor 知道测试将如何进行:首先,老师会给每个学生两个正整数 $$$a$$$ 和 $$$b$$$ ($$$a < b$$$)。之后,学生可以多次应用以下任意操作:

- $$$a := a + 1$$$ (将 $$$a$$$ 增加 $$$1$$$),
- $$$b := b + 1$$$ (将 $$$b$$$ 增加 $$$1$$$),
- $$$a := a \ | \ b$$$ (将 $$$a$$$ 替换为 $$$a$$$ 和 $$$b$$$ 的按位或)。

要在测试中获得满分,学生必须告诉老师使 $$$a$$$ 和 $$$b$$$ 相等所需的最少运算次数。

Igor 已经知道老师会给他哪些数字。帮助他算出使 $$$a$$$ 等于 $$$b$$$ 所需的最少运算次数是多少。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$a$$$ 和 $$$b$$$ ($$$1 \le a < b \le 10^6$$$)。

保证所有测试用例的$$$b$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,打印一个整数 - 使 $$$a$$$ 和 $$$b$$$ 相等所需的最少操作数。

示例

输入 #1

5
1 3
5 8
2 5
3 19
56678 164422

输出 #1

1
3
2
1
23329

注意

在第一个测试用例中,最好应用第三个操作。

在第二个测试用例中,最好应用第一个操作三次。

在第三个测试用例中,最好应用第二个操作,然后应用第三个操作。