Woburn Challenge 2001

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 (i.e. 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 \le X \le 1\,048\,575)~, 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 Specification

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 Specification

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