时间限制：1秒　　内存限制：256M

---

题目描述

有 \(N\) 名学生（\(1 \le N \le 10^5\)），每一名的身高都是 \(1\) 到 \(N\) 的整数。小H 想要拍摄学生以一种特定的顺序排成一行的照片。如果学生们排成一行时从左到右有身高 \(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\)。

小H 希望照片中包含尽可能多的学生。具体地说，小H 可以移除一些学生并重新排列余下的学生。计算 小H 在满足他的限制的情况下可以在照片中包含的学生的最大数量。

输入格式

你需要回答多个测试用例。
输入的第一行包含一个整数 \(T\)（\(1 \leq T \leq 10^5\)），为测试用例的数量。以下为 \(T\) 个测试用例。

每一个测试用例的第一行包含一个整数 \(N\)。第二行包含 \(N\) 个整数，为可用的 \(N\) 名学生的身高。学生们的身高在 \(1\) 到 \(N\) 之间。

输入保证所有测试用例的 \(N\) 之和不超过 \(10^6\)。

输出格式

输出 \(T\) 行，第 \(i\) 行包含第 \(i\) 个测试用例的答案。每行包含一个整数，表示 小H 可以在照片中包含的学生的最大数量。

输入输出样例 #1

输入 #1

2
4
1 1 2 3
4
3 3 2 1

输出 #1

3
1

说明/提示

对于第一个测试用例，小H 可以选择身高为 \(1\)，\(1\) 和 \(3\) 的学生，并重新排列为 \([1,3,1]\)，满足所有条件。对于第二个测试用例，小H 可以选择身高为 \(3\) 的学生以组成一张合法的照片。

• 测试点 \(2\sim3\)：\(T\le 100\)，\(N \le 7\)。
• 测试点 \(4\sim5\)：\(T \le 10^4\)，所有学生的身高不超过 \(10\)。
• 测试点 \(6\sim11\)：没有额外限制。