Problem Statement

For a positive integer $X$, let $f(X)$ be the number of $1$s that appear when $X$ is represented in binary notation. For example, $6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)}$, so $f(6) = 2, \ f(11) = 3, \ f(16) = 1$.

You are given a positive integer $N$. Determine whether there is a positive integer $X$ less than or equal to $N$ such that $f(X) = 3$, and if so, find the maximum such $X$.

There are $T$ test cases to solve.

Constraints

• $1 \leq T \leq 10^5$
• $1 \leq N \leq 10^{18}$

Input

The input is given from Standard Input in the following format, where $N_i$ represents the value of $N$ in the $i$-th test case:

T
N_1
N_2
\vdots
N_T

Output

Print $T$ lines. The $i$-th line should contain the maximum positive integer $X$ less than or equal to $N_i$ such that $f(X) = 3$. If there is no such positive integer $X$, print -1.