← 返回题目列表

Codeforces · 1973/B

B. 猫、狐狸和孤独的阵列

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

今天,Cat 和 Fox 发现了一个由 $$$n$$$ 非负整数组成的数组 $$$a$$$。

将 $$$a$$$ 的孤独度定义为最小正整数 $$$k$$$ ($$$1 \le k \le n$$$),这样对于任何两个正整数 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i, j \leq n - k +1$$$),以下成立: $$$$$$a_i | a_{i+1} | \ldots | a_{i+k-1} = a_j | a_{j+1} | \ldots | a_{j+k-1},$$$$$$ 其中 $$$x | y$$$ 表示$$$x$$$ 和$$$y$$$ 的按位或。换句话说,对于每个 $$$k$$$ 连续元素,它们的按位或应该相同。请注意,$$$a$$$ 的孤独性是明确定义的,因为对于 $$$k = n$$$ ,条件得到满足。

猫和狐狸想知道数组 $$$a$$$ 有多孤独。帮助他们计算找到的数组的孤独度。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i < 2^{20}$$$) — 数组的元素。

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

输出

对于每个测试用例,打印一个整数 - 给定数组的孤独度。

示例

输入 #1

7
1
0
3
2 2 2
3
1 0 2
5
3 0 1 4 2
5
2 0 4 0 2
7
0 0 0 0 1 2 4
8
0 1 3 2 2 1 0 3

输出 #1

1
1
3
4
4
7
3

注意

在第一个示例中,具有单个元素的数组的孤独度始终为 $$$1$$$,因此答案为 $$$1$$$。

在第二个例子中,长度为 $$$k = 1$$$ 的每个子数组的 OR 为 $$$2$$$,因此整个数组的孤独度为 $$$1$$$。

在第七个示例中,$$$(0 | 1 | 3) = (1 | 3 | 2) = (3 | 2 | 2) = (2 | 2 | 1) = (2 | 1 | 0) = (1 | 0 | 3) = 3$$$ 成立,因此 $$$k = 3$$$ 满足条件。我们可以验证对于任何较小的$$$k$$$,该条件都不成立,因此答案确实是$$$3$$$。