2023 年上海市大学生程序设计竞赛 - 一月赛

B. Sets

单点时限: 2.0 sec

内存限制: 512 MB

Amuzi is going to play a game with sets.

Firstly, he has a set $A={1,2,3,\dots,n}$ and 2 empty sets $B$ and $C$. He will put some elements in $A$ into $B$ (Note that each element in $A$ will be chosen no more than once). After that, for $\forall x,y\in B$ , he will put $(x-y)$ into $C$.

Amuzi doesn’t like the number $5$ and $8$, so he doesn’t want these two numbers to be in $C$.

Now Amuzi wants to maximize the size of $B$, can you tell him the maximum size of $B$?

输入格式

The first line contains one integer $T(1\leq T\leq 10^5)$ indicating the number of cases.

For the next $T$ lines, each line contains one integer $n(1\leq n\leq 10^9)$ indicating one case.

输出格式

For each case, output one integer in one line indicating the answer.

样例

Input
3
3
6
9
Output
3
5
5