최선의 트리

트리의 차수열(모든 정점의 차수를 임의의 순서로 나열한 것)이 주어진다.

주어진 차수열을 가지는 모든 트리 중에서 최대 매칭이 가장 큰 트리를 찾아라.

첫째 줄에 정수 $t$가 주어진다 ($1 \le t \le 100\,000$). 이는 테스트 케이스의 수이다.

다음 줄들에 $t$개의 테스트 케이스가 주어진다.

각 테스트 케이스의 첫째 줄에 정수 $n$이 주어진다 ($2 \le n \le 200\,000$). 이는 정점의 수이다.

다음 줄에 $n$개의 정수 $d_1, d_2, \ldots, d_n$이 주어진다 ($1 \le d_i \le n - 1$). 이는 트리의 차수열이다.

$\sum d_i = 2(n - 1)$이고, 주어진 차수열을 가지는 트리가 적어도 하나 존재함이 보장된다.

또한 모든 테스트 케이스에서 $n$의 합은 $200\,000$ 이하이다.

각 테스트 케이스마다 주어진 차수열을 가지는 모든 트리 중 최대 매칭의 최댓값을 나타내는 정수 하나를 출력한다.

첫 번째 테스트 케이스에서는 정점 10개짜리 경로를 만들 수 있다. 이 경로는 같은 차수열을 가지면서 최대 매칭이 가능한 한 크다.

두 번째 테스트 케이스에서 가능한 트리는 모든 정점이 한 정점에 연결된 스타 트리뿐이며, 이 트리의 최대 매칭은 1이다.