eolymp
bolt
Try our new interface for solving problems
Problems

The Great XOR

The Great XOR

Time limit 1 second
Memory limit 122 MiB

Given a long integer x, count the number of values of a satisfying the following conditions:

  • a~xor~x > x

  • 0 < a < x

where xor is the bitwise XOR operator.

You are given q queries, and each query is in the form of a long integer denoting x. For each query, print the total number of values of a satisfying the conditions above on a new line.

Input data

The first line contains the number of queries q~(1 \le q \le 10^5). Each of the q subsequent lines contains a long integer describing the value of x~(1 \le x \le 10^{10}) for a query.

Output data

For each query, print the number of values of a satisfying the given conditions on a new line.

Examples

Input example #1
2
2
10
Output example #1
1
5