【普及】异或子数组

给你一个长度为 $n$ 的整数数组 $a[]$，请你求出同时满足以下两个条件的 最长子数组 的长度 ：

• 1、子数组的按位异或（XOR）为 $0$
• 2、子数组包含的 偶数 和 奇数 数量相等。 如果不存在这样的子数组，则输出 $0$。

子数组 是数组中的一个 连续、非空 元素序列。

输入格式

第一行包含 $1$ 个整数 $T$，表示数据组数

每组数据的第一行包含 $1$ 个整数 $n(1 \le n \le 10^{5}$)$

每组数据的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n (1 \le a_i \le 10^9)$

保证所有数据的 $n$ 之和不超过 $2 \times 10^5$

输出格式

对于每组数据输出 $1$ 行包含 $1$ 个数，表示 最长子数组 的长度

3
5
3 1 3 2 0
8
3 2 8 5 4 14 9 15
1
0

4
8
0

提示

【样例 1 解释】

• 子数组 $[1, 3, 2, 0]$ 的按位异或为 1 ^ 3 ^ 2 ^ 0 = 0
• 且包含 2 个偶数和 2 个奇数

【样例 2 解释】

• 整个数组的按位异或为 $0$
• 且包含 $4$ 个偶数和 $4$ 个奇数

【样例 3 解释】 没有非空子数组同时满足两个条件

【数据范围】

• $1 \le T \le 10^{4}$
• $1 \le n \le 10^{5}$
• $0 \le a_i \le 10^9$
• 保证同一组内的 $n$ 之和不超过 $2 \times 10^5$

来源

• 参考答案