题目描述

今天奶牛们的心情特别顽皮！Farmer John 只是想拍摄一张奶牛们排成一行的照片，但她们总是在他得到机会按下快门之前移动位置。

具体地说，FJ 的 $N$ 头奶牛（$1 \le N \le 10^5$）每一头的身高都是 $1$ 到 $N$ 的整数。FJ 想要拍摄奶牛以一种特定的顺序排成一行的照片。如果奶牛们排成一行时从左到右有身高 $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$。

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

输入格式

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

每一个测试用例的第一行包含一个整数 $N$。第二行包含 $N$ 个整数，为可用的 $N$ 头奶牛的身高。奶牛们的身高在 $1$ 到 $N$ 之间。

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

输出格式

输出 $T$ 行，第 $i$ 行包含第 $i$ 个测试用例的答案。每行包含一个整数，表示 FJ 可以在照片中包含的奶牛的最大数量。

2
4
1 1 2 3
4
3 3 2 1

3
1

提示

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

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