N. Kira needs problems
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Coach $$$Apraham$$$ informed $$$Kira$$$ that the Homs-CPC would be held soon and requested that they

draft some competition problems.

$$$Kira$$$ proposed this particular problem, considering it to be an easy task, and now requests your solution.

You are given a non-negative integer $$$n$$$.

Count the number of non-negative integers $$$x$$$ such that :

  • $$$n + x = n \oplus x $$$, where $$$\oplus$$$ denotes bitwise XOR.
  • $$$x$$$ ($$$0 \le x \le 2^{30}$$$ -$$$1$$$)
Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), the number of test cases.

Then $$$T$$$ test cases as follow.

Each test case consists of a single linecontains one integer $$$n$$$ ($$$0 \le n \le 2^{30}$$$ -$$$1$$$).

Output

For each test case, print a single integer on a separate line: Print the number of valid integers $$$x$$$ .

Example
Input
1
125634
Output
2097152