bete

Se dau $N$ bețe de bambus având lungimile $L_1$, $L_2$, $\dots$, $L_N$. Conform unei tradiții străvechi, două bețe sunt în armonie dacă au aceeași lungime. Întrucât cele $N$ lungimi pot diferi, nu este evident cum se pot face perechi de bețe armonioase. Astfel, se pot alege două bețe și în cazul în care unul dintre ele este mai lung, acesta va fi tăiat la o lungime corespunzătoare cu a celuilalt, pentru a armoniza cu perechea sa. Surplusul este adăugat la grupul de bețe deja existente, iar perechea este lăsată separat, să armonizeze îndelung pentru a aduce noroc și prosperitate. Procedeul de mai sus este repetat succesiv până când, fie toate bețele sunt epuizate, fie se va obține un singur băț.

Cerinţe

Dându-se $Q$ seturi de bețe, să se determine pentru fiecare set, care este cea mai mică lungime posibilă a bățului final, nearmonizat.

Date de intrare

Fişierul de intrare bete.in conţine pe primul rând numărul $Q$, reprezentând numărul seturilor de bețe. Urmează apoi $Q$ linii, conținând numere separate prin câte un spațiu, fiecare linie desemnând un set de bețe. Astfel, primul număr din cadrul unei linii va reprezenta numărul $N$ al bețelor din cadrul setului, fiind urmat de lungimile lor $L_1$, $L_2$, $\dots$, $L_N$.

Date de ieșire

În fişierul de ieşire bete.out se vor scrie $Q$ numere, fiecare pe câte o linie, reprezentând răspunsul asociat fiecărui set de date.

Restricții și precizări

• $1 \leq Q, N \leq 10^4$
• $1 \leq L_k \leq 100$
• Numărul total al bețelor din cadrul celor $Q$ seturi nu va depăşi $10^4$.
• Dacă toate bețele sunt epuizate, în fișierul de ieșire se va scrie valoarea $0$.

Exemplu

bete.in

2
3 2 3 5
5 2 3 3 3 10

bete.out

0
1

Explicație

Setul $1$: $L = \{2, 3, 5 \}$

• se armonizează $3$ cu $5 \rightarrow L = \{2, 2 \}$
• se armonizează $2$ cu $2 \rightarrow L = \{ \}$
• lungimea bățului final: $0$

Setul 2: $L = \{2, 3, 3, 3, 10 \}$

• se armonizează $2$ cu $10 \rightarrow L = \{3, 3, 3, 8 \}$
• se armonizează $3$ cu $8 \rightarrow L = \{3, 3, 5 \}$
• se armonizează $3$ cu $5 \rightarrow L = \{2, 3 \}$
• se armonizează $2$ cu $3 \rightarrow L = \{1 \}$
• lungimea bățului final: $1$