Description

题目描述

给你两个不同的非负整数 $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$ 的长度。换句话说，在某个 $i, j \ge 1$ 中，找出 $a_i = b_j, a_{i + 1} = b_{j + 1}, \ldots, a_{i + m - 1} = b_{j + m - 1}$ 的最大整数 $m$ 。

$^\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$ ) - 序列参数。

输出格式

对于每个测试用例，输出一个整数 - 最长公共子段的长度。

4
0 1
12 4
57 37
316560849 14570961

1
8
4
33554432

说明/提示

注

在第一个测试用例中，序列 $a$ 和 $b$ 的第一个 $7$ 元素如下：

$a = [1, 2, 3, 4, 5, 6, 7,\ldots]$

$b = [0, 3, 2, 5, 4, 7, 6,\ldots]$

可以证明不存在一个正整数 $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, \ldots]$

$b = [36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, \textbf{41, 40, 43, 42}, 53, 52, 55, 54, 49, \ldots]$

可以证明，最长的公共子序列之一是长度为 $4$ 的子序列 $[41, 40, 43, 42]$ 。

$50 \%$的数据，$1 \le x,y \le 2^{10}$

$100 \%$的数据，$1 \le x,y \le 10^9$