I. I take from the richer
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Z-tube Cat is studying how to efficiently activate the "Rat" skill in the board game Legends of the Three Kingdoms.

Rat: You may choose another player whose number of cards is greater than yours, and then take one card from them.

There are $$$n$$$ players in total, and you are player $$$1$$$. Initially, player $$$i$$$ has $$$a_i$$$ cards.

Determine the maximum number of cards you can have after activating Rat any number of times (possibly zero).

Input

Each test contains multiple test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 10^4$$$), the number of test cases.

For each test case:

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the number of players.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$), where $$$a_i$$$ denotes the initial number of cards of player $$$i$$$.

It is guaranteed that, within each test, the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output a single integer on a line — the maximum number of cards you can have after activating Rat any number of times.

Example
Input
2
3
0 3 1
4
0 2 3 0
Output
2
2