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 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) % M$.

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) % M$ (operatorul $%$ 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)$. În meciul cu numărul $i$ ($i ≥ 1$) câştigă primul jucător (cel cu identificatorul mai mic) dacă $x{~i~}$ impar, respectiv al doilea jucător daca $x{~i~}$ este par.