Best Tree

You are given the degree sequence of a tree (the degrees of all its vertices listed in arbitrary order).

Among all trees with the given degree sequence, find a tree whose maximum matching is as large as possible.

The first line contains one integer $t$ ($1 \le t \le 100\,000$): the number of test cases.

The following lines contain $t$ test cases.

The first line of each test case contains one integer $n$ ($2 \le n \le 200\,000$): the number of vertices.

The next line contains $n$ integers $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le n - 1$): the degree sequence of a tree.

It is guaranteed that $\sum d_i = 2(n - 1)$ and that at least one tree has the given degree sequence.

It is also guaranteed that the sum of $n$ over all test cases is at most $200\,000$.

For each test case, print one integer: the largest maximum matching among all trees with the given degree sequence.

In the first test case, you can build a path with 10 vertices. This path has the same degree sequence and the largest possible maximum matching.

In the second test case, the only possible tree is a star (one vertex connected to all the others), and its maximum matching is 1.