Xorstanta

A long time ago in 2018, the National Olympiad in Informatics was held in the city of Constanta. Every contestant was deeply upset that none of the tasks in the problem set was named Xorstanta.

You are given a number $N$. You also have two variables $a = 0$ and $b = 0$ and for each number $i$ from $1$ to $N$ you have to choose between $a = a \oplus i$ and $b = b \oplus i$. Output the largest value for $a + b$ possible given the number $N$.

$\oplus$ represents the bitwise XOR operation.

Input

The first line contains the number of tests you have to solve, $T$ ($1 \leq T \leq 10^5$).
For each test you have a line containing the number $N$ ($1 \leq N \leq 10^9$).

For tests worth $10\%$ of the points, $1 \leq N \leq 20$ and $T = 1$.
For tests worth extra $20\%$ of the points, $1 \leq N \leq 10^5$ and $T = 1$.

Output

Each line contains the solution to the test you are solving.

Example

stdin

4
6
30
15
18

stdout

7
31
30
43