## Problem 3: Austin Powers III, Act II: Back to the Future

P constructs the time machine outlined in Act I and has traveled back in time to this question (Act I is problem 8). However, there is a slight problem in the programming. The machine works in binary, but by a LIFO (last-in, first-out) queue for all numbers that it processes. Therefore, when you type in a number (in base 10) corresponding to the time period you wish to travel to, it converts it to binary (like all computers) but then reads it in LIFO order. Therefore, the last binary digit in the binary representation of the time period (ie. the leftmost digit) is the first one read and the first digit (the rightmost one) is the last one read.

The net result is that to compensate for P’s inadequate programming skills, you need to do the following: If you wish to go to time period X (0 ≤ X ≤ 1048575), you need to convert X to binary, reverse the bit order and then convert back to base 10. This final number is the one that you will actually enter into the computer. Making this calculation is your task.

### Input

The first line of the input contains T, the number of test cases.
The remaining T lines of the input each contain a number X to be converted (in its original base 10 format).

### Output

For each input, output the final number in base 10 (i.e. with reversed bit order) on a separate line.

### Sample Input

```3 64 0 897112```

### Sample Output

```1 0 106715```

Point Value: 5
Time Limit: 2.00s
Memory Limit: 16M