Given a long integer , count the number of values of satisfying the following conditions:
where 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.
The first line contains the number of queries . Each of the subsequent lines contains a long integer describing the value of for a query.
For each query, print the number of values of satisfying the given conditions on a new line.