write a go solution for Description:
You are given a multiset S. Initially, S=1,2,3,ldots,n.

You will perform the following operation n-1 times.

- Choose the largest number S_max in S and the smallest number S_min in S. Remove the two numbers from S, and add S_max-S_min into S.

It's easy to show that there will be exactly one number left after n-1 operations. Output that number.

Input Format:
Each test contains multiple test cases. The first line contains a single integer t (1<=t<=10^5) — the number of test cases. Their description follows.

For each test case, one single line contains a single integer n (2<=n<=10^9) — the initial size of the multiset S.

Output Format:
For each test case, output an integer denoting the only number left after n-1 operations.

Note:
We show how the multiset S changes for n=4.

- Operation 1: S=1,2,3,4, remove 4, 1, add 3.
- Operation 2: S=2,3,3, remove 3, 2, add 1.
- Operation 3: S=1,3, remove 3, 1, add 2.
- Final: S=2.

Thus, the answer for n=4 is 2.. Output only the code with no comments, explanation, or additional text.