这是这个问题的简单版本。简单版本和困难版本之间的区别仅在于 $$$a_i$$$ 和 $$$n$$$ 上的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
布伦卡是布里亚特的王储妃,很快她将成为该国第$$$n$$$女王。布里亚特有一个古老的传统——在加冕之前,统治者必须向居民展示他们的实力。为了确定第 $$$n$$$ 位统治者的实力,该国的居民给他们一个由 $$$a$$$ 组成的数组,其中恰好有 $$$n$$$ 个数字,之后统治者必须在最短的时间内将数组中的所有元素变成零。标尺可以多次执行以下两步操作:
- 选择两个索引 $$$l$$$ 和 $$$r$$$,使得 $$$1 \le l \le r \le n$$$ 和一个非负整数 $$$x$$$,然后
- 对于所有 $$$l \leq i \leq r$$$ 分配 $$$a_i := a_i \oplus x$$$,其中 $$$\oplus$$$ 表示按位异或运算。执行此操作需要 $$$\left\lceil \frac{r-l+1}{2} \right\rceil$$$ 秒,其中 $$$\lceil y \rceil$$$ 表示 $$$y$$$ 四舍五入到最接近的整数。
帮助布伦卡计算她需要多少时间。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 数组的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 5000$$$) — 数组的元素。
保证所有测试中$$$n$$$的总和不超过$$$5000$$$。
输出
对于每个测试用例,输出一个数字 - Burenka 需要的最短时间。
示例
输入 #1
7 4 5 5 5 5 3 1 3 2 2 0 0 3 2 5 7 6 1 2 3 3 2 1 10 27 27 34 32 2 31 23 56 52 4 5 1822 1799 57 23 55
输出 #1
2 2 0 2 4 7 4
注意
在第一个测试用例中,Burenka 可以选择段 $$$l = 1$$$、$$$r = 4$$$ 和 $$$x=5$$$。因此它将在 $$$2$$$ 秒内用零填充数组。
在第二个测试用例中,Burenka 首先选择段 $$$l = 1$$$、$$$r = 2$$$ 和 $$$x = 1$$$,然后 $$$a = [0, 2, 2]$$$,然后选择段 $$$l = 2$$$、$$$r = 3$$$ 和 $$$x=2$$$,其中用零填充数组。布伦卡总共将花费 $$$2$$$ 秒。