近似三元删除

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定数组 $a_1,a_2,\ldots,a_n$。每次可以选择相邻且不相等的两个元素，将它们同时删除；剩余部分自动拼接。

求经过若干次操作后，能够得到的所有元素都相等的数组的最大长度。空数组也视为满足条件。

输入格式

第一行包含测试用例数 $t$。每个测试用例第一行包含 $n$，第二行包含 $n$ 个整数 $a_i$。

输出格式

对每个测试用例输出一个整数。

样例输入 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\le t\le1000$；
• $1\le n\le5000$；
• $1\le a_i\le n$；
• 所有测试用例的 $n$ 之和不超过 $10^4$。