题目描述

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

具体地说，翁老师的 $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$ 之和不超过 $10^6$ 。

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

3
1

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

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

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