$N$ elevi participă la o tabără de tenis, unde fiecare pereche de elevi joacă exact un meci pe durata taberei. În total se joacă $N*(N-1)/2$ meciuri, fiecare terminându-se cu victoria unuia dintre participanţi. La finalul taberei, fiecare jucător primeşte o diplomă de jucător profesionist (înainte de primirea diplomei este considerat amator), în cadrul ceremoniei de premiere.

După ce s-au decernat $K$ diplome, vom avea $K$ jucători profesionişti şi $N-K$ amatori. Vom nota cu $T{~K~}$ numărul total de meciuri pierdute de profesionişti în faţa amatorilor, la momentul $K$.

După ce s-au decernat $K$ diplome, vom avea $K$ jucători profesionişti şi $N-K$ amatori. Vom nota cu $P{~K~}$ numărul total de meciuri pierdute de profesionişti în faţa amatorilor, la momentul $K$.

Organizatorii doresc să decerneze diplomele într-o anumită ordine, astfel încât valoarea maximă a lui $T{~K~}$, $0 ≤ K ≤ N$ să fie cât mai mică. Determinaţi această valoare minimă.

Organizatorii doresc să decerneze diplomele într-o anumită ordine, astfel încât valoarea maximă a lui $P{~K~}$, $0 ≤ K ≤ N$ să fie cât mai mică. Determinaţi această valoare minimă.

h2. Date de intrare

Fişierul de intrare $tenis.in$ conţine pe prima linie numărul de teste $T$. Fiecare test va conţine pe prima linie numărul de elevi $N$, iar pe a doua linie $N*(N-1)/2$ întregi cu rezultatele meciurilor. Meciurile s-au desfăşurat în ordinea $(1, 2); (1, 3); ... (1, N); (2, 3), ... (2, N)$

Fişierul de intrare $tenis.in$ conţine pe prima linie numărul de teste $T$. Fiecare test va conţine pe prima linie numărul de elevi $N$, iar pe a doua linie $N*(N-1)/2$ întregi cu rezultatele meciurilor. Meciurile s-au desfăşurat în ordinea $(1, 2); (1, 3); ... (1, N); (2, 3); ... (2, N); ... (N-1, N)$. Rezultatul unui meci este $1$ dacă primul jucător (cel cu identificatorul mai mic) a câştigat, respectiv $2$ dacă a câştigat al doilea.

h2. Date de ieşire

În fişierul de ieşire $tenis.out$ ...

Fişierul de ieşire $tenis.out$ conţine $T$ linii, câte una pentru fiecare test din fişierul de intrare. Pentru fiecare test se va scrie în fişier valoarea minimă (a numărului maxim de meciuri pierdute de profesionişti în faţa amatorilor) determinată.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 5000$

h2. Exemplu