给定一个整数 $$$n$$$ 和一个数组 $$$a_1,a_2,\ldots,a_n$$$。
在一次操作中,您可以为 $$$a_i \neq a_{i+1}$$$ 选择索引 $$$i$$$ ($$$1 \le i \lt n$$$) 并从数组中删除 $$$a_i$$$ 和 $$$a_{i+1}$$$。删除 $$$a_i$$$ 和 $$$a_{i+1}$$$ 后,数组的其余部分被连接起来。
例如,如果 $$$a=[1,4,3,3,6,2]$$$,则执行 $$$i=2$$$ 运算后,结果数组将为 $$$[1,3,6,2]$$$。
通过执行几个(也许没有)上述操作,从 $$$a$$$ 获得的相等元素数组的最大可能长度是多少?
输入
每个测试包含多个测试用例。输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) - 测试用例的数量。以下行包含测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5000$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$10\,000$$$。
输出
对于每个测试用例,打印一个整数,即通过执行一系列操作从 $$$a$$$ 获得的相等元素数组的最大可能长度。
示例
输入 #1
5 7 1 2 3 2 1 3 3 1 1 6 1 1 1 2 2 2 8 1 1 2 2 3 3 1 1 12 1 5 2 3 3 3 4 4 4 4 3 3
输出 #1
3 1 0 4 2
注意
对于第一个测试用例,最佳操作顺序为:$$$[1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3]$$$。
对于第二个测试用例,数组中的所有元素都已经相等。
对于第三个测试用例,唯一可能的操作顺序是:$$$[1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow []$$$。注意,根据声明,每一步删除的元素必须不同。
对于第四个测试用例,最佳操作顺序是:$$$[1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1]$$$。
对于第五个测试用例,两个相等元素的一个可能可达数组是 $$$[4,4]$$$。