#P18030. OR Preference

OR Preference

OR Preference

给定长度为 NN 的非负整数序列 AA。重复进行以下操作,直到序列只剩一个数:

  • 选择两个相邻元素,用它们的按位与(AND)替换这两个元素;或
  • 选择两个相邻元素,用它们的按位或(OR)替换这两个元素。

每次操作使序列长度减少 11。要求最终剩下的数为 00,求最多可以进行多少次 OR 操作。如果不能使最终结果为 00,输出 −1-1。

输入格式

第一行一个整数 TT。每组测试包含两行:第一行一个整数 NN,第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

每组测试输出一行,表示 OR 操作的最大次数,或 -1。

数据范围

1≤T≤40961\le T\le4096,2≤N≤81922\le N\le8192,0≤Ai≤81910\le A_i\le8191。同一输入文件中所有测试的 NN 之和不超过 81928192。所有输入均为整数。

样例 1

输入:

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

输出:

3
0
5
6