Card Pairs

You have a hand of cards, and each card has one of $n$ types. For each $i$ from $1$ to $n$, you have $a_i$ cards of type $i$, and the bank has an unlimited supply of cards of every type.

You can trade with the bank any number of times. In each trade, choose two cards of the same type from your hand and exchange them for one card from the bank. The new card may have any type from $1$ to $n$ except the type of the two cards you gave up. The bank has no cards of other types, so you cannot receive them.

The image below shows a valid sequence of trades on the first sample case.

What is the maximum number of trades you can perform?

The first line contains a single integer $t$ ($1 \le t \le 10^5$), the number of test cases. Each test case starts with a line containing $n$ ($2 \le n \le 2 \cdot 10^5$), the number of card types. The next line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$), where $a_i$ is the number of cards of type $i$ you currently have. The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

For each test case, print the maximum number of trades you can perform on its own line.

The image above shows an optimal sequence of trades in the first test case.

In the fourth test case, you have no pair of cards with the same type, so no trade is possible and the answer is $0$.