Description

杰克被女神问的一道题难住了：输入一个非负整数（十进制），输出该数的二进制位翻转之后的数（十进制）。

他百思不得其解，机智的你能帮帮他吗？

Format

Input

第一行一个数$T（T<=100）$，表示数据组数，

接下来T行，每行一个非负整数$a（a<=10^9）$，表示每一个询问。

Output

每行一个整数，表示答案。

Samples

3
6
8
1

3
1
1

Limitation

1s, 1024KiB for each test case.