問題文

長さ $N$ の数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます。

任意の $1 \leq s, t \leq N$ なる整数 $s, t$ に対して以下の条件を満たすような、整数 $X$ の最大値を求めてください。

• 変数 $i$ があり、$i = s$ で初期化されている。以下の操作を $0$ 回以上の好きな回数行うことで、$i = t$ にすることができる。
• $A_i \times A_j \geq X$ なる整数 $j$ を一つ選ぶ。$i$ を $j$ に更新する。

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

制約

• $1 \leq T \leq 10^4$
• 各テストケースについて、以下の制約をすべて満たす。
• $2 \leq N \leq 2 \times 10^5$
• $-10^9 \leq A_i \leq 10^9$
• 一つの入力ファイルにおける $N$ の総和は $2 \times 10^5$ 以下である。
• 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられます。ここで $\mathrm{case}_k ~ (1 \leq k \leq T)$ は $k$ 番目のテストケースを表します。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

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

$N$
$A_1$ $A_2$ $\ldots$ $A_N$

出力

$T$ 行出力してください。$k$ 行目には $k$ 番目のテストケースについての答えを出力してください。

サンプル

3
3
1 -2 3
2
1000000000 999999999
9
9 9 -8 2 -4 -4 3 -5 3

-2
999999999000000000
-8