Dana jest sekwencja stopni wierzchołków drzewa (stopnie wszystkich jego wierzchołków, w dowolnej kolejności). Wśród wszystkich drzew o podanej sekwencji stopni, znajdź drzewo z największym możliwym dopasowaniem maksymalnym (maximum matching).

Wejście

Pierwsza linia wejścia zawiera jedną liczbę całkowitą $t$ ($1 \le t \le 100\,000$): liczbę zestawów danych. Kolejne linie zawierają $t$ opisów zestawów danych. Pierwsza linia każdego zestawu danych zawiera jedną liczbę całkowitą $n$ ($2 \le n \le 200\,000$): liczbę wierzchołków. Następna linia zawiera $n$ liczb całkowitych $d_1, d_2, \dots, d_n$ ($1 \le d_i \le n - 1$), będących sekwencją stopni wierzchołków drzewa. Gwarantuje się, że $\sum d_i = 2(n - 1)$ oraz że istnieje co najmniej jedno drzewo o podanej sekwencji stopni. Ponadto gwarantuje się, że suma $n$ we wszystkich zestawach danych wynosi co najwyżej $200\,000$.

Wyjście

Dla każdego zestawu danych wypisz jedną liczbę całkowitą: rozmiar największego dopasowania maksymalnego wśród wszystkich drzew o podanej sekwencji stopni.

Przykład

Wejście 1

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

Wyjście 1

5
1

Uwagi

W pierwszym zestawie danych można skonstruować ścieżkę o 10 wierzchołkach; będzie ona miała tę samą sekwencję stopni i największe możliwe dopasowanie maksymalne. W drugim zestawie danych jedynym możliwym drzewem jest gwiazda (jeden wierzchołek połączony ze wszystkimi pozostałymi), a największe dopasowanie dla niej wynosi 1.