Kareem Salah is a college boy who likes to play with all kinds of numbers. One day he was very bored and decided to play around with even numbers. He writes N numbers on a paper and then, he modifies only even numbers (for some reason he doesn’t want to change odd numbers). He reverses the octal representation of the number and prints it in the decimal representation. But soon he gets bored and asks you to help in order to automate the conversion process.

Input

The first line contains the value of N (1 <= N <= 100), followed by N lines, each line contains a single positive integer A_i (0 <= A_i <= 10¹⁸).

Output

The output will contain N lines, the numbers that are on the blackboard after the conversion process.

Example

Input:
5
10
8
3
5
2 

Output:
17
1
3
5
2

Note

For the first number, the octal representation of the number 10 is 12, when we reverse it, it becomes 21, the number 21 in decimal is 17.