Given a long integer , count the number of values of satisfying the following conditions:
where and are long integers and is the bitwise XOR operator.
You are given queries, and each query is in the form of a long integer denoting . For each query, print the total number of values of satisfying the conditions above on a new line.
For example, you are given the value . Condition requires that . The following tests are run:
We find that there are values meeting the first condition: and .
Complete the theGreatXor function in the editor below. It should return an integer that represents the number of values satisfying the constraints.
theGreatXor has the following parameter(s):
The first line contains an integer , the number of queries.
Each of the next lines contains a long integer describing the value of for a query.
For of the maximum score:
For each query, print the number of values of satisfying the given conditions on a new line.
Sample Input 0
Sample Output 0
We perform the following queries:
For , the following values of satisfy our conditions:
There are five valid values of .
Sample Input 1
Sample Output 1
In the first case:
In the second case, the first 10 values are: