Given a number N in decimal form, you have to cyclically rotate left the binary representation of number N until you get the maximum number that can be formed.

Input

The input contains T, denoting the number of test cases. Each test case contains a number N.

Constraints:

1 <= T <= 100

1 <= N <= (2^32)-1

Input:

2

1

0

Output:

2147483648

0

How to approach this question?