在 Bajtowie 剛舉辦了一場盛大的 Bajt: Bitmingham 遊戲錦標賽。每一場比賽都需要剛好三名玩家在同一個地點會合才能進行。

如你所知，Bajtowie 只有一條長路，路旁有 $n$ 棟建築物，依序編號為 $1$ 到 $n$。

為了方便玩家，規定若三名玩家分別住在編號為 $a, b, c$ 的建築物中，則比賽將在這些建築物中位於中間的那一個舉行，也就是編號為 $a, b, c$ 的中位數之建築物。特別地，若有兩名玩家住在同一棟建築物 $x$，則無論第三名玩家住在何處，比賽都會在建築物 $x$ 舉行。

你正在準備錦標賽的統計摘要。已知每三名玩家之間最多只進行過一次比賽。對於每一棟建築物，你知道其中進行了多少場比賽：對於編號為 $i$ 的建築物，共進行了 $a_i$ 場比賽。然而，你忘記記錄錦標賽中總共有多少名玩家。

請計算在不與現有資訊矛盾的前提下，參與錦標賽的最少玩家人數。

你必須解決 $t$ 個獨立的測試案例。

輸入格式

第一行包含一個整數 $t$ ($1 \le t \le 50$)，代表測試案例的數量。

每個測試案例由兩行組成。第一行包含一個整數 $n$ ($1 \le n \le 200\,000$)，代表 Bajtowie 的建築物數量。第二行包含一個整數序列 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$)，代表各建築物中進行的比賽場數。你可以假設至少有一個 $a_i$ 為正數。

所有測試案例的 $n$ 之總和不超過 $200\,000$。

輸出格式

輸出應包含 $t$ 行，第 $i$ 行應包含一個整數，代表可能參與錦標賽的最少人數。

範例

範例輸入 1

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

範例輸出 1

3
9
5
6

說明

範例說明：在第一個測試案例中，進行一場比賽需要 3 名玩家。在第二個測試案例中，共有 57 場比賽；8 名玩家是不夠的，因為那樣最多只能組成 $\binom{8}{3} = 56$ 種不同的三人組合，因此需要第 9 名玩家。在第三個測試案例中，每棟建築物可能住有一名玩家： 在第二棟建築物中，進行了來自建築物 1, 2, 3；1, 2, 4 以及 1, 2, 5 的玩家之間的比賽； 在第三棟建築物中，進行了來自建築物 1, 3, 4；1, 3, 5；2, 3, 4 以及 2, 3, 5 的玩家之間的比賽； * 在第四棟建築物中，進行了來自建築物 1, 4, 5；2, 4, 5 以及 3, 4, 5 的玩家之間的比賽。

在第四個測試案例中，5 名玩家是不夠的，因為在某棟建築物中最多只有兩名玩家，這不足以組成 4 個具有適當中位數的三人組合。