B. And Xor Pair
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the distant land of Bitland, where all things operate based on binary logic, there exists a powerful artifact known as the "Bitstone." For centuries, it has maintained balance and order throughout the kingdom. However, one fateful day, the Bitstone began to lose its power, and chaos spread across the land.

The royal scholars discovered that the artifact's energy, symbolized by a number $$$n$$$, represents the current instability of the Bitstone. The only way to restore balance is to find two magical numbers $$$x$$$ and $$$y$$$ that satisfy the ancient binary laws of Bitland:

1. $$$(x \oplus y) = n$$$

2. $$$(x \& y) = 2n$$$

As a skilled programmer, you have been called upon to find how many such valid pairs $$$(x,y)$$$ exist for a given $$$n$$$ and help restore balance to Bitland before the chaos becomes irreversible.

Input

The first line contains a single integer $$$t(1 \le t \le 10^3)$$$ — the number of test cases.

Each test case contains a single integer $$$n (0 \le n \le 10^{15})$$$ — the imbalance of the Bitstone.

Output

For each test case, output a single integer representing the number of distinct valid pairs $$$(x, y)$$$ that can stabilize the Bitstone and restore peace to the kingdom.

Example
Input
7
0
1
8
10
12
17
21
Output
1
2
2
4
0
4
8
Note

For $$$n = 0$$$, we need to find pairs $$$(x, y)$$$ such that:

1. $$$(x \oplus y) = 0$$$ (which means $$$x = y$$$)

2. $$$(x \& y) = 0$$$

The only possible solution in this case is $$$(0, 0)$$$ and the answer is $$$1$$$.

For $$$n = 1$$$, we need to find pairs $$$(x, y)$$$ such that:

1. $$$(x \oplus y) = 1$$$ (which means $$$x$$$ and $$$y$$$ must have a bit difference only at the lowest bit.)

2. $$$(x \& y) = 2$$$ (both $$$x$$$ and $$$y$$$ must have a bit set at the second position.)

So, the valid pairs are $$$(2,3)$$$ and $$$(3,2)$$$, and the answer is $$$2$$$.