A. Shuffle Partytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou are given an array a_1, a_2, \ldots, a_n. Initially, a_i=i for each 1 \le i \le n.The operation \texttt{swap}(k) for an integer k \ge 2 is defined as follows:   Let d be the largest divisor^\dagger of k which is not equal to k itself. Then swap the elements a_d and a_k. Suppose you perform \texttt{swap}(i) for each i=2,3,\ldots, n in this exact order. Find the position of 1 in the resulting array. In other words, find such j that a_j = 1 after performing these operations.^\dagger An integer x is a divisor of y if there exists an integer z such that y = x \cdot z.InputEach test contains multiple test cases. The first line contains the number of test cases t (1 \le t \le 10^4). The description of the test cases follows.The only line of each test case contains one integer n (1 \le n \le 10^9) — the length of the array a.OutputFor each test case, output the position of 1 in the resulting array.ExampleInput
4145120240229Output
1
4
4
67108864
NoteIn the first test case, the array is [1] and there are no operations performed.In the second test case, a changes as follows:  Initially, a is [1,2,3,4].  After performing \texttt{swap}(2), a changes to [\underline{2},\underline{1},3,4] (the elements being swapped are underlined).  After performing \texttt{swap}(3), a changes to [\underline{3},1,\underline{2},4].  After performing \texttt{swap}(4), a changes to [3,\underline{4},2,\underline{1}]. Finally, the element 1 lies on index 4 (that is, a_4 = 1). Thus, the answer is 4.
4145120240229
1 4 4 67108864 
['implementation', 'math', '*800']