Se dau N bețe de bambus având lungimile L[1], L[2], …, 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ța

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], …, 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 ≤ Q, N ≤ 10.000
• 1 ≤ L[k] ≤ 100
• Numărul total al bețelor din cadrul celor Q seturi nu va depăși 10.000.
• 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 => L={2, 2}
- se armonizează 2 cu 2 => L={}
- lungimea bățului final: 0
Setul 2: L={2, 3, 3, 3, 10}
- se armonizează 2 cu 10 => L={3, 3, 3, 8}
- se armonizează 3 cu 8 => L={3, 3, 5}
- se armonizează 3 cu 5 => L={2, 3}
- se armonizează 2 cu 3 => L={1}
- lungimea bățului final: 1