I. The Math Guy
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Omar helps George prepare tests on polygons.

Now George is thrilled, so he gives Omar an array of size $$$n$$$ as a present, where each element $$$a_i$$$ is equal to $$$i$$$, starting from $$$1$$$ and ending at $$$n$$$.

As Omar is "The Math Guy" he immediately starts doing these operations on the array $$$n$$$ times in order:

  1. Remove the $$$\dagger$$$Median of the array.
  2. Add the $$$\ddagger$$$MEX of the array to his score.

Can you tell Omar his final score?

$$$\dagger$$$Median of the array is the element in position $$$\lceil \frac{n}{2} \rceil$$$ of the array. Median of $$$[1,2,3,4]$$$ is $$$2$$$ , Median of $$$[1,2,3]$$$ is $$$2$$$.

$$$\ddagger$$$MEX is the minimum positive number not present in the array. MEX of $$$[]$$$ is $$$1$$$, MEX of $$$[1,3,5]$$$ is $$$2$$$.

Input

The first line contains the number of test cases $$$t$$$ $$$( 1 \le t \le 10^{5} )$$$. A description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$( 1 \le n \le 10^{9} )$$$ indicating the size of the array.

Output

For each test case print a single integer represents Omar's final score.

Example
Input
2
1
2
Output
1
2