ストーリー

yukimy32 さんは、自分の誕生日である $1,1,0,6$ が含まれる数列が大好きです。

問題文

非負整数 $n$ に対して、$n$ を leading-zero をつけない $2$ 進数で表したときの $0$ の個数を $f(n)$ とします。ただし、$f(0)=1$ とします。例えば、$f(11)=1, f(32)=5$ です。

長さ $N$ の非負整数列 $A$ が 0-indexed で与えられます。非負整数 $L$ であって、$0 \le i < N$ に対し、$f(L+i)=A_i$ を満たすものが存在するか判定し、存在するならば $L$ としてありえる最小の非負整数、存在しないならば $-1$ を出力してください。

$T$ ケース与えられるので、それぞれに対して答えを求めてください。

制約

• 入力は全て整数
• $1 \le T$
• $1 \le N$
• $0 \le A_i \le 60 (0 \le i < N)$
• $N$ の総和は $10^6$ 以下

入力

$T$
$case_1$
$case_2$
$\vdots$
$case_T$

各テストケースは以下の形式で与えられます。

$N$
$A_0 \ A_1 \ \ldots \ A_{N-1}$

出力

各ケースごとに、条件を満たす $L$ が存在するならばそのうち最小のものを、存在しないならば $-1$ を $1$ 行に出力し、最後に改行してください。

サンプル

3
4
1 1 0 6
2
2 0
1
1

61
-1
0