H. Last Numbertime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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_{\text{max}} in S and the smallest number S_{\text{min}} in S. Remove the two numbers from S, and add S_{\text{max}} - S_{\text{min}} into S. It's easy to show that there will be exactly one number left after n-1 operations. Output that number.InputEach test contains multiple test cases. The first line contains a single integer t (1 \le t \le 10^5) — the number of test cases. Their description follows.For each test case, one single line contains a single integer n (2 \le n \le 10^9) — the initial size of the multiset S.OutputFor each test case, output an integer denoting the only number left after n-1 operations.ExampleInput
524715177567Output
1
2
2
4
33914
NoteWe 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.
524715177567
1 2 2 4 33914 
['combinatorics', 'math', '*2900']