配点 : $400$ 点

問題文

正整数 $X$ に対し，「 $X$ を $2$ 進法表記したときに現れる $1$ の個数」を $f(X)$ とします． たとえば，$6 = 110_{(2)}, \ 11 = 1011_{(2)}, \ 16 = 10000_{(2)}$ なので，$f(6) = 2, \ f(11) = 3, \ f(16) = 1$ です．

正整数 $N$ が与えられます． $N$ 以下の正整数 $X$ であって，$f(X) = 3$ を満たすものが存在するかどうかを判定し，存在するならその最大値を求めてください．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

制約

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

入力

入力は以下の形式で標準入力から与えられる． $N_i$ は $i$ 番目のテストケースにおける $N$ の値を表す．

$T$

$N_1$

$N_2$

$\vdots$

$N_T$

出力

$T$ 行出力せよ． $i$ 行目には，$N_i$ 以下の正整数 $X$ であって，$f(X) = 3$ を満たすものの最大値を出力せよ． ただし，そのような正整数 $X$ が存在しない場合には -1 を出力せよ．

4
16
161
4
1000000000000000000

14
161
-1
936748722493063168

• $1$ つ目のテストケースについて，$f(14) = 3, \ f(15) = 4, \ f(16) = 1$ なので，$X \leq 16$ かつ $f(X) = 3$ を満たす最大の正整数 $X$ は $14$ です．
• $2$ つ目のテストケースについて，$f(161) = 3$ なので，$X \leq 161$ かつ $f(X) = 3$ を満たす最大の正整数 $X$ は $161$ です．
• $3$ つ目のテストケースについて，$f(1) = 1, \ f(2) = 1, \ f(3) = 2, \ f(4) = 1$ なので，$X \leq 4$ かつ $f(X) = 3$ を満たす正整数 $X$ は存在しません．
• $4$ つ目のテストケースのように，入出力値が 32bit 整数型に収まらないこともあります．