Even if it's a really easy question, she won't be able to answer it— Perfect Memento in Strict Sense

Cirno's perfect bitmasks classroom has just started!

Cirno gave her students a positive integer $x$. As an assignment, her students need to find the minimum positive integer $y$, which satisfies the following two conditions:

$$x\ \texttt{and}\ y \gt 0$$x\ \texttt{xor}\ y \gt 0$$</p><p>Where$\texttt{and}$is the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>, and$\texttt{xor}$$$ is the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). Among the students was Mystia, who was truly baffled by all these new operators. Please help her! ## Input The first line of input contains a single integer $t$ ($1 \leq t \leq 10^3$) — the number of input test cases. For each test case, the only line of input contains one integer $x$ ($1 \leq x \leq 2^{30}$). ## Output For each test case, print a single integer — the minimum number of $y$. ## Note Test case 1: $1\; \texttt{and}\; 3=1 \gt 0$, $1\; \texttt{xor}\; 3=2 \gt 0$. Test case 2: $2\; \texttt{and}\; 3=2 \gt 0$, $2\; \texttt{xor}\; 3=1 \gt 0$. ## Samples ```input1 7 1 2 5 9 16 114514 1000000 ``` ```output1 3 3 1 1 17 2 64 ```$$