题目描述

如果一个数列的长度可以表示为 $x + y + x$（$x$ 和 $y$ 是整数且都可以为 $0$），并且存在两个整数 $a$ 和 $b$，满足数列的前 $x$ 个元素和后 $x$ 个元素的数值均为 $a$，且数列中间的 $y$ 个元素的数值均为 $b$，则我们称这个数列为 三段回文数列。比如：

• 数列 $[]$、$[2]$、$[1,2,1]$、$[1,2,2,1]$、$[1,1,2,1,1]$ 都是三段回文数列；
• 数列 $[1,2,3,2,1]$、$[1,2,1,2,1]$、$[1,2]$ 都不是三段回文数列。

本题中，给定一个长度为 $n$ 的数列 $a_1, a_2, \ldots, a_n$，你需要求出数列 $a$ 的是三段回文数列的最长子序列的长度。

输入格式

输入包含多组测试数据，输入的第一行包含一个整数 $t(1 \le t \le 2000)$，表示测试数据组数。

接下来每组测试数据包含两行。第一行包含一个整数 $n(1 \le n \le 2000)$，表示数列长度。
第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n(1 \le a_i \le 10^9)$。

数据保证所有测试数据的 $n$ 之和不超过 $2000$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示数列 $a$ 的最长的是三段回文数列的子序列长度。

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

7
2
4
1
1
3

说明/提示

数据规模与约定

• 对于 $30\%$ 的数据，$t \le 2, n \le 20, a_i \le 1000$

• 对于 $60\%$ 的数据，$t \le 20, n \le 200, a_i \le 10^6$

• 对于 $100\%$ 的数据，$1 \le t \le 2000, 1 \le n \le 2000, 1 \le a_i \le 10^9$，且所有测试数据的 $n$ 之和不超过 $2000$