配列 $a_1,a_2,\ldots,a_n$ の「消化」を、次のように定義します。

• 長さ $n$ の任意の順列 $p_1,p_2,\ldots,p_n$ を選びます（$1$ から $n$ までの整数からなる配列で、各整数がちょうど一度ずつ現れるものです）。
• すべての $i$ について、$a_i:=a_i\bmod\max(a_{p_i},1)$ を同時に実行します。
• 配列から取り除く数 $a_i$ を任意に一つ選び、残りを連結して新しい配列 $a_1,a_2,\ldots,a_{n-1}$ を作ります。この配列が消化操作の結果です。

この手順で得られる任意の配列が、消化操作の結果になり得ます。

$1$ から $n$ までの整数からなる配列 $a_1,a_2,\ldots,a_n$ が与えられます。この配列に対して消化操作を連続して $n-1$ 回行った後に得られる $a_1$ の値の最大値はいくつでしょうか？

入力

各テストは複数のテストケースからなります。最初の行には、テストケースの数を表す整数 $t$（$1\le t\le 10^4$）が与えられます。続く行に各テストケースの記述が与えられます。

各テストケースの最初の行には、配列 $a$ の長さを表す整数 $n$（$1\le n\le 2\cdot 10^5$）が与えられます。

各テストケースの二行目には、配列 $a$ の要素を表す $n$ 個の整数 $a_1,a_2,\ldots,a_n$（$1\le a_i\le n$）が与えられます。

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

出力

各テストケースについて、得られる $a_1$ の値の最大値を出力してください。

入出力例

入力 1

1
3
3 2 2

出力 1

1