简单版本和困难版本之间的唯一区别是限制。
给定一个由 $$$n$$$ 正整数组成的序列 $$$a$$$。
让我们定义一个三块回文作为序列,最多由两个不同的元素组成(让这些元素是 $$$a$$$ 和 $$$b$$$,$$$a$$$ 可以等于 $$$b$$$),如下所示: $$$[\underbrace{a, a, \dots, a}_{x}, \underbrace{b, b, \dots, b}_{y}, \underbrace{a, a, \dots, a}_{x}]$$$。其中$$$x,y$$$是大于或等于$$$0$$$的整数。例如,序列 $$$[]$$$、$$$[2]$$$、$$$[1, 1]$$$、$$$[1, 2, 1]$$$、$$$[1, 2, 2, 1]$$$ 和 $$$[1, 1, 2, 1, 1]$$$ 是三个块回文,但 $$$[1, 2, 3, 2, 1]$$$、$$$[1, 2, 1, 2, 1]$$$ 和 $$$[1, 2]$$$ 不是。
你的任务是选择 $$$a$$$ 的最大长度子序列,它是一个三块回文。
您必须回答 $$$t$$$ 独立测试用例。
回想一下,如果 $$$t$$$ 可以通过删除零个或多个元素而不改变剩余元素的顺序从 $$$s$$$ 导出,则序列 $$$t$$$ 是序列 $$$s$$$ 的子序列。例如,如果 $$$s=[1, 2, 1, 3, 1, 2, 1]$$$,则可能的子序列为:$$$[1, 1, 1, 1]$$$、$$$[3]$$$ 和 $$$[1, 2, 1, 3, 1, 2, 1]$$$,但不是 $$$[3, 2, 3]$$$ 和$$$[1,1,1,1,2]$$$。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2000$$$) — 测试用例的数量。然后是 $$$t$$$ 测试用例。
测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) — $$$a$$$ 的长度。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 26$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。请注意,$$$a_i$$$ 的最大值可达 $$$26$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$ ($$$\sum n \le 2000$$$)。
输出
对于每个测试用例,打印答案 - $$$a$$$ 的某些子序列的最大可能长度,该子序列是一个三块回文。
示例
输入 #1
6 8 1 1 2 2 3 2 1 1 3 1 3 3 4 1 10 10 1 1 26 2 2 1 3 1 1 1
输出 #1
7 2 4 1 1 3