题目描述

在集训结束时，翁老师会要求所有学生站队拍照留念。但有些同学比较顽皮，会在按下快门之前移动位置。

具体地说，翁老师 的 $n$ 个学生 每一个人的身高都是 $1$ 到 $n$ 的整数。翁老师 想要拍摄学生以一种特定的顺序排成一行的照片。如果学生们排成一行时从左到右有身高 $h_1, \dots, h_k$，他希望同学们的身高拥有以下三个性质：

• 他希望同学们的身高先递增再递减。形式化地说，必须存在一个整数 $i$ 使得 $h_1 \le \dots \le h_i \ge \dots \ge h_k$。
• 他不希望任何同学与另一位身高完全相同的同学相邻。形式化地说，对于所有 $1 \le i < k$ 有 $h_i \neq h_{i+1}$。
• 他希望照片是对称的。形式化地说，如果 $i + j = k+1$，则 $h_i = h_j$。

翁老师 希望照片中包含尽可能多的同学。具体地说，翁老师 可以让一些同学暂离队伍并重新排列余下的同学。计算 翁老师 在满足他的限制的情况下可以在照片中包含的同学的最大数量。

输入格式

本题有多组数据

输入的第一行包含一个整数 $t$，为测试数据组数。每一组数据：

• 第一行输入一个整数 $n$。
• 第二行输入 $n$ 个整数表示每位同学的身高。

输入保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

输出 $t$ 行，第 $i$ 行包含第 $i$ 组数据的答案。

2
4
1 1 2 3
4
3 3 2 1

3
1

提示

样例解释

对于第一组数据，翁老师 可以选择身高为 $1$，$1$ 和 $3$ 的同学，并重新排列为 $[1,3,1]$，满足所有条件。

对于第二个组数据，翁老师 可以选择身高为 $3$ 的同学以组成一张合法的照片。

数据范围

• 对于 $30\%$ 的数据满足：$1\leq t\leq 100$，$1\leq n\leq 7$。
• 对于 $50\%$ 的数据满足：$1\leq t\leq 10^4$，，所有同学的身高均不超过 $10$。
• 对于 $100\%$ 的数据满足：$1\leq t\leq 10^5$，$1\leq n\leq 10^5$。

保证 $\sum n\leq 10^6$。