Se te proporciona la secuencia de grados de un árbol (los grados de todos sus vértices, en orden arbitrario). Entre todos los árboles con la secuencia de grados dada, encuentra un árbol con el emparejamiento máximo más grande.

Entrada

La primera línea de la entrada contiene un entero $t$ ($1 \le t \le 100\,000$): el número de casos de prueba. Las siguientes líneas contienen $t$ descripciones de un caso de prueba. La primera línea de cada caso de prueba contiene un entero $n$ ($2 \le n \le 200\,000$): el número de vértices. La siguiente línea contiene $n$ enteros $d_1, d_2, \dots, d_n$ ($1 \le d_i \le n - 1$), la secuencia de grados de un árbol. Se garantiza que $\sum d_i = 2(n - 1)$ y que existe al menos un árbol con la secuencia de grados dada. Además, se garantiza que la suma total de $n$ en todos los casos de prueba es como máximo $200\,000$.

Salida

Para cada caso de prueba, imprime un entero: el emparejamiento máximo más grande entre todos los árboles con la secuencia de grados dada.

Ejemplos

Entrada 1

2
10
1 1 2 2 2 2 2 2 2 2
5
4 1 1 1 1

Salida 1

5
1

Nota

En el primer caso de prueba, puedes construir un camino con 10 vértices; tendrá la misma secuencia de grados y el emparejamiento máximo más grande posible. En el segundo caso de prueba, el único árbol posible es una estrella (un vértice conectado con todos los demás), y el emparejamiento más grande para este es 1.