#JMFESTEST018. T1孤独的数列

T1孤独的数列

孤独的数列 (lonely, 1s/256M)

某一天,你走在路上的时候,看到地上有一个 nn 个非负整数组成的序列 a1,a2,,ana_1,a_2,\ldots,a_n

你很惊讶地发现:你总是能找到一个正整数 kk,使得这个数列的任意 kk 个连续正整数的按位或的结果都相同!也就是说,对于 i,j (1i,jnk+1)\forall i, j\ (1 \le i, j \le n - k + 1),都有

aiai+1ai+k1=ajaj+1aj+k1a_i | a_{i+1} | \ldots | a_{i+k-1} = a_j | a_{j+1} | \ldots | a_{j + k - 1}

那么,我们定义能找到的最小的 kk 就是这个序列的 “孤独程度”。你的任务是找到给定的 TT 个序列的每个序列的孤独程度。

输入格式

第一行一个正整数 TT,表示序列个数。

对于每一个序列,第一行输入一个正整数 nn,表示序列中的元素个数。第二行输入 nn 个由空格隔开的整数 a1,a2,,ana_1,a_2,\ldots,a_n

输出格式

对于每个序列,输出一行一个整数,表示给定数组的孤独度。

样例输入

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,所以答案是 1。

在第二个示例中,每个长度为 1 的子数组的按位或运算结果都是 2,所以整个数组的孤独度是 1。

第七个样例,最终找到 k=3k=3 时,长度为 3 的子数组:

[0, 1, 3] -> 0 | 1 | 3 = 3
[1, 3, 2] -> 1 | 3 | 2 = 3
[3, 2, 2] -> 3 | 2 | 2 = 3
[2, 2, 1] -> 2 | 2 | 1 = 3
[2, 1, 0] -> 2 | 1 | 0 = 3
[1, 0, 3] -> 1 | 0 | 3 = 3

每个长度为 3 的子数组的按位或运算结果都相同(为 3),因此孤独度为 3。最终输出结果为 3。

数据范围

  • 对于 30% 的数据,1n100,n1001 \le n \le 100, \sum n \le 100.
  • 对于 100% 的数据,1n2×105,0ai<220,n4×105,1T1041\le n \le 2\times 10^5, 0 \le a_i < 2^{20}, \sum n \le 4\times 10^5, 1\le T \le 10^4.