Find The Pairs

You are given a non-negative integer N. A pair(a, b) is called atomic if (a | b) = N ("|" means bitwise OR). You have to find number of such atomic pairs. Here, (a | b) and (b | a) are considered as different pairs.
For the first sample test case, for N = 2 , atomic pairs are (2 , 0) , (0 , 2) , (2 , 2).

Input

First line will contain number of test case T. Each subsequent line will contain a number N.
1 ≤ T ≤ 1000
1 ≤ N ≤ $2*10^6$

Output

For each test case output one integer. Number of atomic pair for N.

Sample

Input	Output
1 2	3