Almost Triple Deletions

给定长为 $n$ 的数组 $\{a_n\}$，每次操作可删去数组中相邻的两个不相等的元素（即若 $i\in[1,n), a_i\not=a_{i+1}$，则可以删去 $a_i$ 和 $a_{i+1}$）。求若干次操作后，使得数组内元素全部相等的数组长度的最大值。 多测，$t\le10^3$，$1\le a_i\le n\le5\times10^3$，$\sum n\le10^4$。 Translated by @Sya_Resory

You are given an integer $ n $ and an array $ a_1,a_2,\ldots,a_n $ . In one operation, you can choose an index $ i $ ( $ 1 \le i \lt n $ ) for which $ a_i \neq a_{i+1} $ and delete both $ a_i $ and $ a_{i+1} $ from the array. After deleting $ a_i $ and $ a_{i+1} $ , the remaining parts of the array are concatenated. For example, if $ a=[1,4,3,3,6,2] $ , then after performing an operation with $ i=2 $ , the resulting array will be $ [1,3,6,2] $ . What is the maximum possible length of an array of equal elements obtainable from $ a $ by performing several (perhaps none) of the aforementioned operations?

Each test contains multiple test cases. The first line of input contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The following lines contain the descriptions of the test cases. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 5000 $ ) — the length of array $ a $ . The second line of each test case contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \le a_i \le n $ ) — the elements of array $ a $ . It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 10\,000 $ .

For each testcase, print a single integer, the maximum possible length of an array of equal elements obtainable from $ a $ by performing a sequence of operations.

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

3
1
0
4
2

For the first testcase, an optimal sequence of operations would be: $ [1,2,3,2,1,3,3] \rightarrow [3,2,1,3,3] \rightarrow [3,3,3] $ . For the second testcase, all elements in the array are already equal. For the third testcase, the only possible sequence of operations is: $ [1,1,1,2,2,2] \rightarrow [1,1,2,2] \rightarrow [1,2] \rightarrow [] $ . Note that, according to the statement, the elements deleted at each step must be different. For the fourth testcase, the optimal sequence of operations is: $ [1,1,2,2,3,3,1,1] \rightarrow [1,1,2,3,1,1] \rightarrow [1,1,1,1] $ . For the fifth testcase, one possible reachable array of two equal elements is $ [4,4] $ .