Description

Given $T$ queries, each with a non-negative integer $n$. Find two integers $a$ and $b$ that satisfy the following conditions:

• $0 \le a,b \le n$
• $a \oplus b=n$

$\oplus$ means bitwise xor.

Maximize $a+b$.

Input Format

Each test case contains multiple data sets. You will only receive the score for a test case if you pass all its data sets.

The first line contains an integer $T$.

The next $T$ lines each contains an integer $n$.

Output Format

$T$ lines, each contains an integer representing the maximum of $a+b$.

6
1
2
3
4
5
6

1
2
3
4
5
8

Hint

Example explanation

There are a total of $6$ queries.

• For the fifth query, $a=0,b=n$ is a possible choice;

• For the sixth query, $a=3,b=5$ is a possible choice.

Data Volume and Conventions

This problem is divided into subtasks. Your score in a subtask is the minimum score across all its test cases.

This problem uses subtask dependencies. You will not receive the score for a subtask unless you achieve full points on all its dependent subtasks.

For all of the cases, $1 \le T \le 10^6,0 \le n \le 2^{31}-1$.