Little MS は $n$ 本のナイフを持っており、$i$ 番目のナイフの切断力は $a_i$ です。彼女は巨大なケーキを切り分ける必要がありますが、このとても重要な仕事のために、持っているナイフのうちどれを選べばよいか決められません。

しばらくして、Little MS はナイフの空でない部分集合を一様ランダムに選ぶことにしました（したがって、各部分集合が選ばれる確率は $\frac{1}{2^n-1}$ です）。その後、選んだナイフをすべて任意の順序で使います。切断力が $x$ のナイフは、その時点で存在するケーキの各切れを $x$ 個の小さな切れに分割します。最終的に Little MS が得る切れの数は $a_{i_1}\cdot\ldots\cdot a_{i_k}$ となります。ここで $i_1,\ldots,i_k$ は選んだナイフの番号です。

Little MS が最終的にちょうど $s$ 個のケーキの切れを得る確率が $50\%$ より真に大きくなるような数 $s$ が存在するかどうかを、彼女のために判定してください。

入力

最初の行には、テストケースの数を表す整数 $t$（$1\le t\le 10^4$）が 1 つ与えられます。

各テストケースの最初の行には、ナイフの本数を表す整数 $n$（$2\le n\le 2\cdot 10^5$）が 1 つ与えられます。

各テストケースの 2 行目には、$n$ 個の整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le 10^9$）が与えられます。$a_i$ は $i$ 番目のナイフの切断力です。

すべてのテストケースにわたる $n$ の総和が $2\cdot 10^5$ を超えないことが保証されます。

出力

各テストケースについて、条件を満たす数 $s$ が存在しない場合は $-1$ を出力してください。

それ以外の場合は、Little MS が最終的にちょうど $s$ 個のケーキの切れを得る確率が $50\%$ より真に大きくなるような数 $s$ を出力してください。

入出力例

入力 1

4
2
2 3
2
100 100
3
2 2 2
4
1 1 1 1

出力 1

-1
100
-1
1

注記

最初のテストケースでは、ナイフのすべての空でない部分集合に対して得られる積は $2$、$3$、$6$ です。それぞれ 1 回ずつ現れるので、$50\%$ より真に大きい確率で得られるものはありません。したがって、答えは $-1$ です。

2 番目のテストケースでは、ナイフのすべての空でない部分集合に対して得られる積は $100$、$100$、$10000$ です。積 $100$ は 3 通りのうち 2 通りで現れるため、その確率は $50\%$ より真に大きくなります。したがって、答えは $100$ です。

3 番目のテストケースでは、ナイフのすべての空でない部分集合に対して得られる積は $2$、$2$、$2$、$4$、$4$、$4$、$8$ です。半分を超える回数現れる積はないので、答えは $-1$ です。