给你两个不同的非负整数 $$$x$$$ 和 $$$y$$$。考虑两个无限序列 $$$a_1, a_2, a_3, \ldots$$$ 和 $$$b_1, b_2, b_3, \ldots$$$,其中
- $$$a_n = n \oplus x$$$;
- $$$b_n = n \oplus y$$$。
这里,$$$x \oplus y$$$ 表示整数$$$x$$$ 和$$$y$$$ 的按位异或运算。
例如,当 $$$x = 6$$$ 时,序列 $$$a$$$ 的前 $$$8$$$ 元素将如下所示:$$$[7, 4, 5, 2, 3, 0, 1, 14, \ldots]$$$。请注意,元素的索引以 $$$1$$$ 开头。
你的任务是找到序列$$$a$$$和$$$b$$$的最长公共子段$$$^\dagger$$$的长度。换句话说,找到最大整数 $$$m$$$,使得 $$$a_i = b_j, a_{i + 1} = b_{j + 1}, \ldots, a_{i + m - 1} = b_{j + m - 1}$$$ 对于某些 $$$i, j \ge 1$$$。
$$$^\dagger$$$序列$$$p$$$的子段是序列$$$p_l,p_{l+1},\ldots,p_r$$$,其中$$$1 \le l \le r$$$。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的唯一行包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$0 \le x, y \le 10^9, x \neq y$$$) - 序列的参数。
输出
对于每个测试用例,输出一个整数 - 最长公共子段的长度。
示例
输入 #1
4 0 1 12 4 57 37 316560849 14570961
输出 #1
1 8 4 33554432
注意
在第一个测试用例中,序列 $$$a$$$ 和 $$$b$$$ 的前 $$$7$$$ 元素如下:
$$$a = [1, 2, 3, 4, 5, 6, 7,\l点]$$$
$$$b = [0, 3, 2, 5, 4, 7, 6,\l点]$$$
可以证明,不存在正整数$$$k$$$使得序列$$$[k, k + 1]$$$作为子段出现在$$$b$$$中。所以答案是$$$1$$$。
在第三个测试用例中,序列 $$$a$$$ 和 $$$b$$$ 的前 $$$20$$$ 元素如下:
$$$a = [56, 59, 58, 61, 60, 63, 62, 49, 48, 51, 50, 53, 52, 55, 54, \textbf{41, 40, 43, 42}, 45, \dots]$$$
$$$b = [36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, \textbf{41, 40, 43, 42}, 53, 52, 55, 54, 49, \dots]$$$
可以看出,最长的公共子段之一是长度为$$$4$$$的子段$$$[41,40,43,42]$$$。