問題文

要素数が $2N$ である配列 $\mathcal{A}=[a_1,\dots ,a_N,b_1,\dots ,b_N]$ に対して, $\pi (\mathcal{A})$ を
$\pi (\mathcal{A})=[a_1,b_1,a_2,b_2,\dots ,a_k,b_k,\dots ,a_N,b_N]$
と定める. また, 非負整数 $n$ に対して,
${\pi }^n(\mathcal{A})=\{\begin{array}{ll}\pi ({\pi }^{n-1}(\mathcal{A}))& (n\ge 1)\\ \mathcal{A}& (n=0)\end{array}$
とする.

では, 与えられた正の整数 $N$ に対して, 要素数 $2N$ の配列 $\mathcal{A}$ を
$\mathcal{A}=[1,2,\dots ,2N-1,2N]$
としたとき, 正の整数 $K$ で, ${\pi }^K(\mathcal{A})=\mathcal{A}$ となるものが存在するならば, そのうち最小の正の整数を求め, 存在しなければ, その旨を報告せよ.

なお, 2つの配列 $\mathcal{A}=[x_1,\dots ,x_l],\mathcal{B}=[y_1,\dots ,y_m]$ に対して, $\mathcal{A}=\mathcal{B}$ であるとは,

• $l=m$
• 任意の $i=1,2,\dots ,l(=m)$ に対して,$x_i=y_i$

$T$ 個のテストケースについて答えよ.

制約

• $1\le T\le 100$
• $1\le N\le {10}^9$
• $T,N$ は整数である.

入力

$T$

$N$

出力

${\pi }^K(\mathcal{A})=\mathcal{A}$ を満たす正の整数 $K$ が存在すれば, そのうち最小のものを求めよ. 存在しなければ-1を出力せよ.

サンプル

3
3
2
26

4
2
8