Bessie は自分のアルゴリズムで整数配列をソートしようとしています。$N$ 個の整数 $a_1,a_2,\dots,a_N$ の山があり、$(1 \leq N \leq 2\cdot 10^5)$ と $(1 \leq a_i \leq 10^{11})$ を満たします。これを別の配列に昇順に入れます。繰り返し山の最小値を見つけ、取り除き、配列の末尾に追加します。$p$ 個の整数の山から最小値を見つけるには $p$ 秒かかります。

Farmer John は他の牛にも手伝うよう指示しましたが、牛たちは怠け者なので、Bessie はそれを利用します。整数を自分の山と助手の山に分け、自分の山には通常のアルゴリズムを実行します。助手の山の各整数は別々の助手の牛に割り当てます。農場が大きいので助手は何頭でも呼べます。整数 $a_i$ を受け取った助手には $a_i$ 秒昼寝し、起きたら直ちにその整数を配列の末尾に追加させます。Bessie と助手が同時に追加する場合、リーダーである Bessie の整数が先になります。同じ整数を受け取った助手が複数いれば、その整数のコピーを同時に追加します。

最終配列がソート済みになり、必要な時間が最小になるように整数を分けてください。

入力

最初の行に独立したテストケース数 $T$（$1\le T\le 10$）が与えられます。

各テストケースの形式は次のとおりです。

最初の行に Bessie の配列の整数の個数 $N$ が与えられます。

次の行にソートする整数 $a_1, a_2, \dots, a_N$ が与えられます。同じ整数が複数回現れることがあります。

全テストケースの $N$ の合計は $2\cdot 10^5$ 以下です。

出力

各テストケースについて、最適に分けた場合にソートする最小時間を別々の行に出力してください。

入出力例

入力 1

4
5
1 2 4 5 100000000000
5
17 53 4 33 44
4
3 5 5 5
6
2 5 100 1 4 5

出力 1

6
15
5
6

注記

最初の例では $1,2$ を助手に割り当て、$4,5,10^{11}$ を自分で処理できます。

2 番目の例では、すべて自分でソートするのが最善です。$4$ を助手に、それ以外を自分に割り当てる方法はうまくいきません。助手が $4$ を追加する前に Bessie が $17$ を追加してしまうからです。

3 番目の例では、すべての整数を助手に割り当てられます。

4 番目の例では $1,4,5$ を助手に割り当て、$2,5,100$ を自分で処理できます。

小課題

• 入力 2：$N\le 16$
• 入力 3–5：$N\le 150$
• 入力 6–8：$\sum N\le 5000$
• 入力 9–11：追加の制約はありません。

作問：Suhas Nagar