seuOJ420 - 王嘉然的选课问题

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：1000 ms
• 空间限制：256 MiB
• 题目标签：冬季, 校赛, 决赛, 2022

题目描述

大学一共开设了$n$门课，每一门课都有学分$c_i$，王嘉然可以选择连续的一段课程去学。

• 假如王嘉然学完了$[l,r]$$(1\le l\le r\le n)$之间的课程，那么她就可以获得$(c_l+c_{l+1}+...+c_{r-1}+c_r)-(c_l\bigoplus c_{l+1} \bigoplus ...\bigoplus c_{r-1}\bigoplus c_r)$ 个学分。
• 假如她一门课都不选，那么她就获得 $0$ 个学分。

其中$\bigoplus$表示按位异或。

王嘉然想请你帮帮她，告诉她最少选多少门课就能获得最多的学分。

输入格式

第一行，一个整数$t(1\le t \le 10^4)$代表数据组数。
对于每组数据： 第一行，一个整数$n(1\le n \le 2\times 10^5)$，代表课程数目。
第二行,$n$个整数$a(0\leq a_i \leq 2^{30})$，代表每门课的学分。

保证$1\leq\sum n \leq 2\times 10^5$。

输出格式

对于每组数据，输出一行数字代表王嘉然最少需要上的课程数。

样例

输入样例1:

2
6
1 1 4 5 1 4
5
1 0 2 4 0

输出样例1：

5
0