バイトフ（Bajtów）で、壮大なゲーム「Bajt: Bitmingham」の大会が開催されました。このゲームの1試合には、正確に3人のプレイヤーが参加し、試合を行うためには全員が同じ場所に集まる必要があります。

ご存知の通り、バイトフには1本の長い道路があり、その道沿いに $1$ から $n$ までの番号が振られた $n$ 個の建物が並んでいます。

プレイヤーの便宜を図るため、3人のプレイヤーがそれぞれ $a, b, c$ 番の建物に住んでいる場合、試合はその中間の建物、すなわち $a, b, c$ の中央値である番号の建物で行われると定められました。特に、2人のプレイヤーが同じ建物 $x$ に住んでいる場合、3人目のプレイヤーの居住地に関わらず、試合はその建物 $x$ で行われます。

あなたは大会の統計をまとめる仕事をしています。各3人組のプレイヤーは、最大で1回しか対戦していないことがわかっています。各建物について、そこで何試合行われたかがわかっており、建物 $i$ では $a_i$ 試合が行われました。しかし、大会に何人のプレイヤーが参加したのかを記録し忘れてしまいました。

手元にある情報と矛盾しない、大会に参加したプレイヤーの最小人数を計算してください。

この問題を $t$ 個の独立したテストケースについて解く必要があります。

入力

入力の1行目には、テストケースの数 $t$ ($1 \le t \le 50$) が含まれます。 各テストケースは2行で構成されます。1行目にはバイトフにある建物の数 $n$ ($1 \le n \le 200\,000$) が含まれます。2行目には、各建物で行われた試合数を示す整数の列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$) が含まれます。少なくとも1つの $a_i$ は正であると仮定して構いません。

すべてのテストケースにおける $n$ の合計は $200\,000$ を超えません。

出力

出力は $t$ 行からなり、$i$ 行目には $i$ 番目のテストケースにおける、大会に参加した可能性のある最小の人数を出力してください。

入出力例

入力 1

4
1
1
1
57
5
0 3 4 3 0
2
4 4

出力 1

3
9
5
6

注記

例の解説：最初のテストケースでは、1試合を行うために3人のプレイヤーが必要です。2番目のテストケースでは57試合が行われています。8人のプレイヤーでは $\binom{8}{3} = 56$ 通りの3人組しか作れないため不十分であり、9人目のプレイヤーが必要です。3番目のテストケースでは、各建物に1人ずつプレイヤーが住んでいると仮定できます。

• 2番目の建物では、建物1, 2, 3のプレイヤー間、1, 2, 4のプレイヤー間、および1, 2, 5のプレイヤー間で試合が行われました。
• 3番目の建物では、建物1, 3, 4のプレイヤー間、1, 3, 5のプレイヤー間、2, 3, 4のプレイヤー間、および2, 3, 5のプレイヤー間で試合が行われました。
• 4番目の建物では、建物1, 4, 5のプレイヤー間、2, 4, 5のプレイヤー間、および3, 4, 5のプレイヤー間で試合が行われました。

4番目のテストケースでは、5人のプレイヤーでは不十分です。なぜなら、いずれかの建物に住むプレイヤーが最大でも2人となり、適切な中央値を持つ4つの3人組を作るには足りないからです。