Kothu is attacked by N aliens! Each ith alien has hit points Hi (1<=i<=N). Kothu starts attacking the aliens with experience points XP=1 and FH=0 (FH is the maximum height upto which he can fly).
When confronted with an alien, Kothu can only do one of the following two actions :
Each alien can be defeated only once and Kothu can confront the aliens in any order! Given the respective hit points for each alien, can you find the maximum value that FH will get after Kothu confronts all aliens?
Even if the initial height FH is 0, you can assume that he can fly over any alien of height H if needed.
Input:
The first line of the input contains an integer T, denoting the number of testcases. Each test case is described by two lines
The first line contains an integer N denoting the number of aliens Kothu has to defeat. The second line contains N space separated integers denoting hit points for N aliens (H1, H2, H3,..., HN).
Constraints:
1 <= T <= 10^5
1 <= N <= 10^5
1 <= Hi <= 10^7
Output:
For each testcase, output a single integer denoting the maximum flying height FH that Kothu can acquire .
There are 3 aliens having the following hit points: [3, 2, 2] . Initially XP = 1, and FH = 0. The following is an optimal sequence of actions for achieving the maximum number of experience points possible:
Fly over the second alien (H1 = 2). XP is increased from 1 to 2 , and FH is still 0 .
Kill the first alien (H0 = 3). XP remains the same, but FH increases by XP*H0 = 2*3 = 6 points.
Kill the third alien (H2 = 2). XP remains the same, but FH increases by experience points XP*H2 = 2*2 = 4.
Kothu earns 6+4 = 10 FH points, so we print 10 on a new line.