Z-shaped Pipeline Cat is studying how to efficiently activate the "Zi Shu" skill in Legends of the Three Kingdoms.

Zi Shu: Skill, you may choose another character who has more cards than you, and then obtain one card from them.

There are a total of $n$ characters, and you are the 1st character. Initially, the $i$-th character has $a_i$ cards.

Please find the maximum number of cards you can have after activating "Zi Shu" any number of times (possibly zero).

Input

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

For each test case: The first line contains an integer $n$ ($1 \le n \le 10^6$), representing the number of characters. The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$), where the $i$-th integer $a_i$ represents the initial number of cards of the $i$-th character.

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

Output

For each test case, output a single integer representing the maximum number of cards you can have after activating "Zi Shu" any number of times.

Examples

Input 1

2
3
0 3 1
4
0 2 3 0

Output 1

2
2

Note

For the first test case in the example: You activate "Zi Shu" for the first time: choose the 2nd character and obtain one of their cards. The number of cards for each character becomes 1, 2, 1. You activate "Zi Shu" for the second time: choose the 2nd character and obtain one of their cards. The number of cards for each character becomes 2, 1, 1. Since there are no other characters with more cards than you at this point, you cannot activate "Zi Shu" a third time. It can be proven that the maximum number of cards you can have after activating "Zi Shu" any number of times is 2.

For the second test case in the example: You activate "Zi Shu" for the first time: choose the 3rd character and obtain one of their cards. The number of cards for each character becomes 1, 2, 2, 0. You activate "Zi Shu" for the second time: choose the 2nd character and obtain one of their cards. The number of cards for each character becomes 2, 1, 2, 0. Since there are no other characters with more cards than you at this point, you cannot activate "Zi Shu" a third time. It can be proven that the maximum number of cards you can have after activating "Zi Shu" any number of times is 2.