Vous disposez de la séquence des degrés d'un arbre (les degrés de tous ses sommets, dans un ordre arbitraire). Parmi tous les arbres ayant la séquence de degrés donnée, trouvez un arbre possédant le plus grand couplage maximal.

Entrée

La première ligne de l'entrée contient un entier $t$ ($1 \le t \le 100\,000$) : le nombre de cas de test. Les lignes suivantes contiennent $t$ descriptions de cas de test. La première ligne de chaque cas de test contient un entier $n$ ($2 \le n \le 200\,000$) : le nombre de sommets. La ligne suivante contient $n$ entiers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le n - 1$), la séquence des degrés d'un arbre. Il est garanti que $\sum d_i = 2(n - 1)$ et qu'il existe au moins un arbre avec la séquence de degrés donnée. De plus, il est garanti que la somme totale de $n$ sur tous les cas de test est au plus $200\,000$.

Sortie

Pour chaque cas de test, affichez un entier : la taille du plus grand couplage maximal parmi tous les arbres ayant la séquence de degrés donnée.

Exemples

Entrée 1

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

Sortie 1

5
1

Remarque

Dans le premier cas de test, vous pouvez construire un chemin avec 10 sommets ; il aura la même séquence de degrés et le plus grand couplage maximal possible. Dans le second cas de test, le seul arbre possible est une étoile (un sommet connecté à tous les autres), et le plus grand couplage pour celui-ci est 1.