311352: CF1973B. Cat, Fox and the Lonely Array

B. Cat, Fox and the Lonely Arraytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Today, Cat and Fox found an array $a$ consisting of $n$ non-negative integers.

Define the loneliness of $a$ as the smallest positive integer $k$ ($1 \le k \le n$) such that for any two positive integers $i$ and $j$ ($1 \leq i, j \leq n - k +1$), the following holds: $$a_i | a_{i+1} | \ldots | a_{i+k-1} = a_j | a_{j+1} | \ldots | a_{j+k-1},$$ where $x | y$ denotes the bitwise OR of $x$ and $y$. In other words, for every $k$ consecutive elements, their bitwise OR should be the same. Note that the loneliness of $a$ is well-defined, because for $k = n$ the condition is satisfied.

Cat and Fox want to know how lonely the array $a$ is. Help them calculate the loneliness of the found array.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4 $) — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i < 2^{20}$) — the elements of the array.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $10^5$.

Output

For each test case, print one integer  — the loneliness of the given array.

ExampleInput

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

Output

1
1
3
4
4
7
3

Note

In the first example, the loneliness of an array with a single element is always $1$, so the answer is $1$.

In the second example, the OR of each subarray of length $k = 1$ is $2$, so the loneliness of the whole array is $1$.

In the seventh example, it's true that $(0 | 1 | 3) = (1 | 3 | 2) = (3 | 2 | 2) = (2 | 2 | 1) = (2 | 1 | 0) = (1 | 0 | 3) = 3$, so the condition is satisfied for $k = 3$. We can verify that the condition is not true for any smaller $k$, so the answer is indeed $3$.

题目大意：
题目描述了一个关于数组的问题，定义了数组的“孤独值(loneliness)”。给定一个由非负整数组成的数组a，其“孤独值”是最小的正整数k（1≤k≤n），使得对于任意两个正整数i和j（1≤i,j≤n-k+1），以下条件成立：

a_i | a_{i+1} | ... | a_{i+k-1} = a_j | a_{j+1} | ... | a_{j+k-1}

这里的x | y表示x和y的按位或(bitwise OR)操作。简而言之，对于每k个连续的元素，它们的按位或结果应该是相同的。题目指出，数组的“孤独值”是有明确定义的，因为当k=n时，条件自然满足。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。
- 每个测试用例的描述如下：
- 第一行包含一个整数n（1≤n≤10^5），表示数组a的长度。
- 第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i<2^20），表示数组的元素。
- 保证所有测试用例的n之和不超过10^5。

输出：
- 对于每个测试用例，输出一个整数，表示给定数组的“孤独值”。

示例输入输出：
输入：
```
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
3
4
4
7
3
```

注意：
- 在第一个示例中，单个元素的数组的“孤独值”总是1。
- 在第二个示例中，每个长度为k=1的子数组的按位或都是2，所以整个数组的“孤独值”是1。
- 在第七个示例中，对于k=3，有(0 | 1 | 3) = (1 | 3 | 2) = (3 | 2 | 2) = (2 | 2 | 1) = (2 | 1 | 0) = (1 | 0 | 3) = 3，所以条件对于k=3成立。我们可以验证，对于任何更小的k，条件不成立，所以答案是3。题目大意： 题目描述了一个关于数组的问题，定义了数组的“孤独值(loneliness)”。给定一个由非负整数组成的数组a，其“孤独值”是最小的正整数k（1≤k≤n），使得对于任意两个正整数i和j（1≤i,j≤n-k+1），以下条件成立： a_i | a_{i+1} | ... | a_{i+k-1} = a_j | a_{j+1} | ... | a_{j+k-1} 这里的x | y表示x和y的按位或(bitwise OR)操作。简而言之，对于每k个连续的元素，它们的按位或结果应该是相同的。题目指出，数组的“孤独值”是有明确定义的，因为当k=n时，条件自然满足。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。 - 每个测试用例的描述如下： - 第一行包含一个整数n（1≤n≤10^5），表示数组a的长度。 - 第二行包含n个整数a_1, a_2, ..., a_n（0≤a_i<2^20），表示数组的元素。 - 保证所有测试用例的n之和不超过10^5。 输出： - 对于每个测试用例，输出一个整数，表示给定数组的“孤独值”。 示例输入输出： 输入： ``` 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 3 4 4 7 3 ``` 注意： - 在第一个示例中，单个元素的数组的“孤独值”总是1。 - 在第二个示例中，每个长度为k=1的子数组的按位或都是2，所以整个数组的“孤独值”是1。 - 在第七个示例中，对于k=3，有(0 | 1 | 3) = (1 | 3 | 2) = (3 | 2 | 2) = (2 | 2 | 1) = (2 | 1 | 0) = (1 | 0 | 3) = 3，所以条件对于k=3成立。我们可以验证，对于任何更小的k，条件不成立，所以答案是3。