There are n block towers, numbered from 1 to n. The i-th tower consists of ai blocks.

In one move, you can move one block from tower i to tower j, but only if ai>aj. That move increases aj by 1 and decreases ai by 1. You can perform as many moves as you would like (possibly, zero).

What's the largest amount of blocks you can have on the tower 1 after the moves?

Input

The first line contains a single integer t (1≤t≤104) — the number of testcases.

The first line of each testcase contains a single integer n (2≤n≤2?105) — the number of towers.

The second line contains n integers a1,a2,…,an (1≤ai≤109) — the number of blocks on each tower.

The sum of n over all testcases doesn't exceed 2?105.

Output

For each testcase, print the largest amount of blocks you can have on the tower 1 after you make any number of moves (possibly, zero).

-------------------------------------------------------------

有n座塔樓，編號(hào)從1到n。 第 i 座塔由 ai 塊組成。

一次移動(dòng)，您可以將一個(gè)方塊從 i 塔移動(dòng)到 j 塔，但前提是 ai>aj。 該移動(dòng)使 aj 增加 1，并將 ai 減少 1。您可以執(zhí)行任意數(shù)量的移動(dòng)（可能是零）。

移動(dòng)后 1 號(hào)塔上最多可以擁有多少塊方塊？

輸入

第一行包含一個(gè)整數(shù) t (1≤t≤104) — 測(cè)試用例的數(shù)量。

每個(gè)測(cè)試用例的第一行包含一個(gè)整數(shù) n (2≤n≤2?105) — 塔的數(shù)量。

第二行包含 n 個(gè)整數(shù) a1,a2,…,an (1≤ai≤109) — 每個(gè)塔上的塊數(shù)。

所有測(cè)試用例的 n 總和不超過 2?105。

輸出

對(duì)于每個(gè)測(cè)試用例，在進(jìn)行任意次數(shù)的移動(dòng)（可能為零）后，打印塔 1 上可以擁有的最大塊數(shù)。

----------------------------

只要先找跟a1最接近的值，然后把a(bǔ)1增加后，在繼續(xù)找，所以這里面可以用排序解決，但是我用數(shù)組排序，提交后，超時(shí)了。。。沒辦法就只能有優(yōu)先隊(duì)列了。還好通過了。。

下面是代碼：