The Great XOR

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

• $axorx>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

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

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

Examples