You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Problem Description

圣诞节快到了，kuro决定为他的队友们制作手工巧克力作为礼物。

众所周知，手工巧克力指的是从商店里买来巧克力融化后重新凝固而成的巧克力。商店里有重量分别为$1,2,3...,n$的$n$种巧克力正在售卖(n为偶数)，kuro决定先从商店里购买$k (k > 2)$种巧克力，再从商店中购买3种不同重量的巧克力各两块，重量分别为$a,b,c(a \neq b \neq c)$，将它们重新制作成三种重量为$a+b,a+c,b+c$的巧克力,kuro想将这些手工巧克力混入直接在商店购买的巧克力中不被发现，所以他希望这三块新巧克力的重量都分别和第一次购买的某块巧克力一样。

kuro打算尽量少的购买巧克力，但又希望任意选择从商店购买的巧克力种类都能有办法选择三种巧克力作为手工巧克力的材料，他想知道最少需要购买多少巧克力可以达成目标。

kuro对于这个问题束手无策，只好来求助你了。

形式化的说，求最小的$k$，使得对于集合$A={1,2,..n}$的任意有$k$个元素的子集$S$,都存在三个数$a,b,c \in A,a \neq b \neq c$,满足$a+b,a+c,b+c \in S$

Input Format

第一行为一个整数$T$ ($1 \leq T \leq 1000$)，表示该测试点共有$T$组测试

每组测试的第一行为一个数$n$($6 \leq n \leq 10^9$,n为偶数)，表示商店中的巧克力种类数。

Output Format

对于每组测试，输出一行，包含一个数，代表最小能达成条件的购买数量$k$.

Sample

输入 #1

1
6

输出 #1

6

可以证明，$n=6$时，对于所有$k<6$，都至少有一种买法不存在符合要求的巧克力选法。

例如，当$k=5$时，如果kuro购买的巧克力重量分别为{1,2,3,4,6}，无法选出制作手工巧克力的三种材料。

当$k=6$时，kuro购买的巧克力重量分别为{1,2,3,4,5,6},可以选择重量为{1,2,3}的巧克力制作手工巧克力