$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 maximul numărului total de meciuri câştigate de un amator împotriva unui profesionist din orice moment să fie cât mai mic. Determinaţi

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

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

Î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 ≤ 3000$
* $2 ≤ A, B, M ≤ 100000$
* $1 ≤ T ≤ 30$
 

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

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 2
  2 7 4 9
  5 9 8 15
| 0
  3

|
h3. Explicaţie

...

Î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") ==