兔兔有n个用相同大小的积木叠成的柱子，编号为1到n。第i个柱子由ai块积木组成。
每次操作中，你可以选定两个编号为i和j柱子， 且满足ai>aj，从第i个柱子顶端取下一块积木放在第j个柱子的顶端。
请问经过任意多次操作后，第1个柱子积木数量的最大值是多少？

第一行为整数T,表示有T (1≤T≤10000)组测试样例。
每组测试样例的第一行仅有一个整数n (2≤n≤200000),表示积木柱子的数量。
第二行为n个整数a1,a2,...an (1≤ai≤1e9),表示组成每个柱子的积木数量。
测试数据保证所有的n之和不超过200000。

对于每组测试数据，输出一个整数。表示经过任意多次操作后，第1个柱子积木数量的最大值。

4
3
1 2 3
3
1 2 2
2
1 1000000000
10
3 8 6 7 4 1 2 4 10 1

3
2
500000001
9

在第1组测试数据中，可从柱子2移一块积木到柱子1，得到[2,1,3]，接着从柱子3移一块积木到柱子1，得到[3,1,2]。因此柱子1的积木数量最大值为3。
在第2组测试数据中，可从柱子2或3移一块积木到柱子1，得到柱子1的积木数量最大值为2。
在第3组测试数据中，可重复500000000次将一块积木从柱子2移到柱子1，得到[500000001,500000000]。