Fişierul intrare/ieşire:	tenis.in, tenis.out	Sursă	ad-hoc
Autor	Ciprian Oprisa	Adăugată de	Ciprian Oprisa •cypry
Timp execuţie pe test	0.5 sec	Limită de memorie	16384 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Tenis

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 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 P_K, 0 ≤ K ≤ N să fie cât mai mică. Determinaţi această valoare minimă.

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); ... (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.

Date de ieşire

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ă.

Restricţii

• 2 ≤ N ≤ 5000

Exemplu

Explicaţie

În primul test avem doar 2 jucători, deci un singur meci, în care al doilea jucător câştigă. Dacă ordinea de decernare a diplomelor este 2, 1, la nici un moment de timp nu vom avea profesionişti învinşi de amatori, deci rezultatul este 0.

Cum se trimit solutii?