该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Z 形管道猫正在研究如何高效发动《三国杀》中的“子鼠”。

题目描述

子鼠：技能，您可以选择一名卡牌数大于您的其他角色，然后获得其的一张卡牌。

总共有 $n$ 名角色，您是第 $1$ 名角色。初始，第 $i$ 名角色有 $a_i$ 张卡牌。

请您求出只通过您发动任意次（可以零次）“子鼠”后，您的卡牌数的最大值。

输入格式

每个测试点包含多组测试数据。第一行给定一个整数 $T(1\le T\le 10^4)$，表示测试数据组数。

对于每组测试数据：
第一行给定一个整数 $n(1\le n\le10^6)$，表示角色数。
第二行给定 $n$ 个整数 $a_i(0\le a_i\le10^9)$，其中第 $i$ 个整数 $a_i$ 表示初始第 $i$ 名角色的卡牌数。

保证在每个测试点中所有测试数据的 $n$ 的总和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示只通过您发动任意次“子鼠”后，您的卡牌数的最大值。

输入输出样例 #1

输入 #1

2
3
0 3 1 
4
0 2 3 0

输出 #1

2
2

说明/提示

对于样例的第一组测试数据：
您发动第一次“子鼠”：选择第 $2$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}1},\textbf{\color{red}2},1$。
您发动第二次“子鼠”：选择第 $2$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}2},\textbf{\color{red}1},1$。
因为此时没有卡牌数大于您的其他角色，所以您无法发动第三次“子鼠”。
可以证明，只通过您发动任意次“子鼠”后，您的卡牌数的最大值是 $2$。

对于样例的第二组测试数据：
您发动第一次“子鼠”：选择第 $3$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}1},2,\textbf{\color{red}2},0$。
您发动第二次“子鼠”：选择第 $2$ 名角色，然后获得其的一张卡牌。各角色的卡牌数变为 $\textbf{\color{red}2},\textbf{\color{red}1},2,0$。
因为此时没有卡牌数大于您的其他角色，所以您无法发动第三次“子鼠”。
可以证明，只通过您发动任意次“子鼠”后，您的卡牌数的最大值是 $2$。