小苯的对称序列

题号：NC316020
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一个长度为 $n$ 的数组 $a_1, a_2, \dots, a_n$ 。他定义一种“对称子序列”如下：
$\hspace{15pt}$ 一个子序列 $a_{i_1}, a_{i_2}, \dots, a_{i_m}$ （ $1 \le i_1 < i_2 < \dots < i_m \le n$ ）是对称的，当且仅当它满足：
$\hspace{23pt}\bullet\ a_{i_1} + a_{i_m} = a_{i_2} + a_{i_{m-1}} = \dots = a_{i_{\lceil m/2 \rceil}} + a_{i_{m - \lceil m/2 \rceil + 1}}$
$\hspace{15pt}$ 换句话说，子序列首尾配对的和都相等。

$\hspace{15pt}$ 你的任务是求出数组 $a$ 中最长的对称子序列的长度是多少。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行包含一个整数 。
第二行包含  个整数 。

输出描述:

对于每组测试数据：
输出一个整数，表示最长对称子序列的长度。

示例1

输入

复制

3
5
1 2 3 2 1
6
1 1 2 2 3 3
4
1 100 100 1

输出

复制

3
6
2

说明

第一组数据：可以选择子序列 ，满足：。
第二组数据：整个数组就是一个对称子序列。
第三组数据：可以选择子序列 。