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

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

Fişierul de intrare $tenis.in$ conţine pe prima linie numărul de teste $T$. Fiecare test va fi format dintr-o linie ce conţine patru întregi $N$, $A$, $B$ şi $M$. $N$ reprezintă numărul elevilor, iar $A$, $B$ şi $M$ ne ajută să generăm şirul $x{~i~}$ după următoarea regulă: $x{~0~} = 1$, iar $x{~i+1~} = (A * x{~i~} + B) mod M$ (operatorul $mod$ semnifică restul împărţirii).
 
Se ştie că meciurile s-au desfăşurat în ordinea $(1, 2); (1, 3); ... (1, N); (2, 3); ... (2, N); ... (N-1, N)$. Numerotarea meciurilor începe de la 1. În meciul cu numărul $i$ ( $i ≥ 1$ ) câştigă primul jucător (cel cu identificatorul mai mic) dacă $x{~i~}$ este impar, respectiv al doilea jucător daca $x{~i~}$ este par.

h2. Date de ieşire

h2. Restricţii

* $2 ≤ N ≤ 5000$

* $2 ≤ N ≤ 3000$
* $2 ≤ A, B, M ≤ 100000$
* $1 ≤ T ≤ 30$
 

h2. Exemplu
table(example). |_. tenis.in |_. tenis.out |
| 2

  2
  2
  4
  TBA

  2 7 4 9
  5 9 8 15

| 0

  TBA

  3

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

În primul test avem doar 2 jucători, deci un singur meci. $x{~1~} = (7 * 1 + 4) mod 9 = 2$, care este par, deci 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.

== include(page="template/taskfooter" task_id="tenis") ==