Burenka and Traditions (easy version)

题意翻译

有 $T$ 组数据， 对于每一组数据，你有一个长度为 $n$ 的数组 $a$， 每一次操作可以选择一段区间 $[l,r]$ 和一个非负整数 $x$，花费 $\lceil (r - l + 1) / 2 \rceil$ 秒使区间内的数都异或 $x$， 问最少需要几秒才能把数组中所有的元素变成零

题目描述

This is the easy version of this problem. The difference between easy and hard versions is only the constraints on $ a_i $ and on $ n $ . You can make hacks only if both versions of the problem are solved. Burenka is the crown princess of Buryatia, and soon she will become the $ n $ -th queen of the country. There is an ancient tradition in Buryatia — before the coronation, the ruler must show their strength to the inhabitants. To determine the strength of the $ n $ -th ruler, the inhabitants of the country give them an array of $ a $ of exactly $ n $ numbers, after which the ruler must turn all the elements of the array into zeros in the shortest time. The ruler can do the following two-step operation any number of times: - select two indices $ l $ and $ r $ , so that $ 1 \le l \le r \le n $ and a non-negative integer $ x $ , then - for all $ l \leq i \leq r $ assign $ a_i := a_i \oplus x $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). It takes $ \left\lceil \frac{r-l+1}{2} \right\rceil $ seconds to do this operation, where $ \lceil y \rceil $ denotes $ y $ rounded up to the nearest integer. Help Burenka calculate how much time she will need.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 500 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5000 $ ) — the size of the array. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 5000 $ ) — elements of the array. It is guaranteed that the sum of $ n $ in all tests does not exceed $ 5000 $ .

输出格式

For each test case, output a single number — the minimum time that Burenka will need.

输入输出样例

输入样例 #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

说明

In the first test case, Burenka can choose segment $ l = 1 $ , $ r = 4 $ , and $ x=5 $ . so it will fill the array with zeros in $ 2 $ seconds. In the second test case, Burenka first selects segment $ l = 1 $ , $ r = 2 $ , and $ x = 1 $ , after which $ a = [0, 2, 2] $ , and then the segment $ l = 2 $ , $ r = 3 $ , and $ x=2 $ , which fills the array with zeros. In total, Burenka will spend $ 2 $ seconds.

**布伦卡和传统（简单版本）**

**题意翻译**
- 有 $ T $ 组数据。
- 对于每一组数据，你有一个长度为 $ n $ 的数组 $ a $。
- 每一次操作可以选择一段区间 $[l,r]$ 和一个非负整数 $ x $，花费 $\lceil (r - l + 1) / 2 \rceil$ 秒使区间内的数都异或 $ x $。
- 问最少需要几秒才能把数组中所有的元素变成零。

**题目描述**
这是这个问题的简单版本。简单版本和困难版本之间的区别仅在于对 $ a_i $ 和 $ n $ 的限制。只有当两个版本的问题都解决时，你才能进行黑客攻击。

布伦卡是布里亚特王国的王储，很快她将成为该国的第 $ n $ 位女王。布里亚特有一个古老的传
统——在加冕之前，统治者必须向居民展示他们的力量。为了确定第 $ n $ 位统治者的力量，国家的居民给了他们一个正好有 $ n $ 个数字的数组 $ a $，之后统治者必须以最短的时间将数组的所有元素变为零。统治者可以任意多次执行以下两步操作：

- 选两个索引 $ 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 $。
- **输出格式**：对于每个测试用例，输出一个数字——布伦卡将需要的最少时间。

**输入输出样例**
- **输入样例 #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
```**布伦卡和传统（简单版本）** **题意翻译** - 有 $ T $ 组数据。 - 对于每一组数据，你有一个长度为 $ n $ 的数组 $ a $。 - 每一次操作可以选择一段区间 $[l,r]$ 和一个非负整数 $ x $，花费 $\lceil (r - l + 1) / 2 \rceil$ 秒使区间内的数都异或 $ x $。 - 问最少需要几秒才能把数组中所有的元素变成零。 **题目描述** 这是这个问题的简单版本。简单版本和困难版本之间的区别仅在于对 $ a_i $ 和 $ n $ 的限制。只有当两个版本的问题都解决时，你才能进行黑客攻击。 布伦卡是布里亚特王国的王储，很快她将成为该国的第 $ n $ 位女王。布里亚特有一个古老的传 统——在加冕之前，统治者必须向居民展示他们的力量。为了确定第 $ n $ 位统治者的力量，国家的居民给了他们一个正好有 $ n $ 个数字的数组 $ a $，之后统治者必须以最短的时间将数组的所有元素变为零。统治者可以任意多次执行以下两步操作： - 选两个索引 $ 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 $。 - **输出格式**：对于每个测试用例，输出一个数字——布伦卡将需要的最少时间。 **输入输出样例** - **输入样例 #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 ```