카드 쌍

손에 든 카드마다 $n$가지 종류 중 하나가 정해져 있다. $1$부터 $n$까지의 각 $i$에 대해 종류 $i$의 카드를 $a_i$장 가지고 있고, 은행에는 모든 종류의 카드가 무한히 있다.

은행과의 거래는 원하는 만큼 몇 번이든 할 수 있다. 거래 한 번에는 손에서 같은 종류의 카드 두 장을 고르고, 은행에서 카드 한 장을 받아 교환한다. 받는 카드의 종류는 방금 낸 두 카드의 종류를 제외한 $1$부터 $n$까지 중 어느 것이든 될 수 있다. 은행에는 그 밖의 종류의 카드가 없으므로 다른 종류는 받을 수 없다.

다음 그림은 첫 번째 예제에서 가능한 거래 순서를 보여준다.

거래를 최대 몇 번 할 수 있는지 구하시오.

첫 줄에 테스트 케이스의 수 $t$ ($1 \le t \le 10^5$)가 주어진다. 각 테스트 케이스의 첫 줄에는 카드 종류의 수 $n$ ($2 \le n \le 2 \cdot 10^5$)이 주어진다. 둘째 줄에는 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$)이 주어지며, $a_i$는 지금 가지고 있는 종류 $i$ 카드의 수이다. 모든 테스트 케이스의 $n$을 합한 값은 $2 \cdot 10^5$를 넘지 않는다.

각 테스트 케이스마다 할 수 있는 거래의 최대 횟수를 한 줄에 하나씩 출력한다.

그림은 첫 번째 테스트 케이스에서 최적의 거래 순서를 나타낸다.

네 번째 테스트 케이스에서는 같은 종류의 카드 쌍이 하나도 없어서 거래를 전혀 할 수 없다. 따라서 답은 $0$이다.