== include(page="template/taskheader" task_id="floare") ==

Intr-o zi cand se plictiseau, Ana si prietenele ei au inventat un nou joc, pe care l-au jucat de $T$ ori. Fetele au o floare cu $N$ petale si la o mutare au voie sa rupa minim una si maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $A$~0~ trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $A$~1~ trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $A$~N-1~ trandafiri. Ana poate stabili ordinea in care fetele vor rupe petalele. Ajutati-o, pentru fiecare dintre cele $T$ jocuri, sa castige cat mai multi trandafiri.

Intr-o zi cand se plictiseau, Ana si prietenele ei au inventat un nou joc, pe care l-au jucat de $T$ ori. Fetele au o floare cu $N$ petale si la o mutare au voie sa rupa minim una si maxim $K$ dintre ele. Traditia spune ca norocoasa care ia ultimele petale ale florii va primi $A$~0~ trandafiri rosii, cea care ar fi trebuit sa mute urmatoarea va primi $A$~1~ trandafiri rosii si asa mai departe pana la cea care a mutat exact inainte de castigatoare, care primeste $A$~M-1~ trandafiri. Ana poate stabili ordinea in care fetele vor rupe petalele. Ajutati-o, pentru fiecare dintre cele $T$ jocuri, sa castige cat mai multi trandafiri.

h2. Date de intrare

h2. Restricţii si precizari
* $1 ≤ T ≤ 100$

* $1 ≤ M ≤ 200000$
* $1 ≤ N ≤ 200000$

* $1 ≤ M ≤ 200 000$
* $1 ≤ N ≤ 200 000$
* $1 ≤ K ≤ 200 000$

* Se stie ca fiecare fata joaca optim, adica vrea sa castige cat mai multi trandafiri
* Valorile din sirul $A$ sunt distincte

* Pentru teste in valoare de cel putin $30$ de puncte valorile pentru $N$ vor fi mai mici sau egale cu $1000$

* Pentru teste in valoare de cel putin $30$ de puncte valorile pentru $N$ vor fi mai mici sau egale cu $1 000$

h2. Exemplu

4267