Ted thinks that integers having equal number of 1's and 0's in their binary representation are special. Therefore, he wants to know how many such integers are present.

Note: For this problem, the binary representation of an integer(>0) is considered from the least significant bit to the last set bit. Which means, 5 has a binary representation of 101, 3 has a binary representation of 11 etc. As such, one example of a special number is 9 which has a binary representation, 1001.

Input

First line contains an integer T (at most 100) denoting the total number of test cases. Each test case contains a single integer N (2 <= N <= 2^60). N is always a power of 2.

Output

A single integer denoting the total number of such special numbers in the range 1 to N (inclusive).

Example

Input:
3
8
16
32

Output:
1
4
4