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

În drumul lor către oraşul Zalău, Bulănel şi Bulăniţa au hotărât să joace un joc pentru a alunga plictiseala.
 
Cei doi au la dispoziţie un grid cu $N$ linii (numerotate de la $1$ la $N$) şi $M$ coloane (numerotate de la $1$ la $M$). Bulănel începe jocul prin plasarea unui pătrat pe o celulă a gridului. Scopul jocului este acoperirea gridului înaintea celuilalt jucător. La fiecare pas, un jucător alege o direcţie (nord, est, sud, vest) si extinde figura rectangulară în direcţia respectivă cu maxim $K$ linii (dacă direcţia aleasă a fost nord sau sud) sau maxim $K$ coloane (dacă direcţia aleasă a fost est sau vest). La nici un moment al jocului, nu se poate extinde figura în afara gridului. Jucătorul care nu mai poate extinde figura în nicio direcţie este declarat pierzător. După ce Bulănel plasează pătratul iniţial, Bulăniţa e cea care face prima extindere.
 
De exemplu, dacă ar juca pe un grid de $N = 3$ linii şi $M = 5$ coloane şi ar alege $K = 3$, jocul s-ar putea desfăşura în felul următor:
 
| !problema/aiacujoc?01.jpg! | !problema/aiacujoc?02.jpg! | !problema/aiacujoc?03.jpg! |
| *Pasul 1*: Bulănel plasează pătratul pe linia $2$, coloana $5$ | *Pasul 2*: Bulăniţa extinde figura cu $2$ coloane în vest. | *Pasul 3*: Bulănel extinde figura cu $1$ linie în nord. |
| !problema/aiacujoc?04.jpg! | !problema/aiacujoc?05.jpg! | !problema/aiacujoc?06.jpg! |
| *Pasul 4*: Bulăniţa extinde figura cu $1$ linie în sud. | *Pasul 5*: Bulănel extinde figura cu $1$ coloană în vest. | *Pasul 6*: Bulăniţa extinde figura cu $1$ coloană în vest. |
 
Bulănel pierde jocul acesta din cauză că nu mai poate extinde figura în nici o direcţie. Totuşi, Bulănel ar fi putut câştiga jocul dacă ar fi făcut o serie diferită de mişcări (de exemplu, dacă ar fi extins figura cu $2$ coloane în vest în loc de $1$, în pasul 5) sau dacă ar fi plasat pătratul iniţial pe o altă poziţie.
 
h2. Cerinţă
 
Cei doi hotărăsc să joace mai multe jocuri. Ajutaţi-l pe Bulănel să afle, pentru fiecare joc, numărul de poziţii în care poate plasa pătratul iniţial astfel încât să aibă strategie de câştig, adică să poată câştiga indiferent de mutările Bulăniţei.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $aiacujoc.in$ conţine pe prima linie numărul natural $T$, reprezentând numărul de jocuri pe care Bulănel şi Bulăniţa o să-l joace. Pe fiecare din următoarele $T$ linii, se află câte trei numerele naturale care definesc un joc: numărul natural $N$, reprezentând numărul de linii ale gridului, urmat de numărul natural $M$, reprezentând numărul de coloane ale gridului, urmat de numărul natural $K$, reprezentând numărul maxim de linii sau de coloane cu care un jucător poate extinde figura la un anumit pas.

Fişierul de intrare $aiacujoc.in$ ...

h2. Date de ieşire

Fişierul de ieşire $aiacujoc.out$ va conţine $T$ linii. Pe fiecare linie $i$, se va afla câte un număr natural care reprezintă numărul de poziţii de pe grid unde Bulănel poate plasa pătratul iniţial, care îi asigură lui Bulănel strategie câştigătoare pentru al $i$-lea joc.

În fişierul de ieşire $aiacujoc.out$ ...

h2. Restricţii

* Pentru toate testele, $1 ≤ T ≤ 10$.
* Pentru teste în valoare de $5$ puncte, $N = 1$, $1 ≤ M ≤ 20$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $5$ puncte, $1 ≤ N, M ≤ 20$, $K ≥ max(N, M)$, $N$ şi $M$ au parităţi diferite.
* Pentru alte teste în valoare de $10$ puncte, $1 ≤ N, M ≤ 20$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $30$ de puncte, $1 ≤ N, M ≤ 1 000$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $10$ de puncte, $1 ≤ N, M ≤ 1 000 000$, $K ≥ max(N, M)$.
* Pentru alte teste în valoare de $20$ de puncte, $1 ≤ N, M, K ≤ 1 000 000$.
* Pentru alte teste în valoare de $10$ de puncte, $1 ≤ N, M ≤ 1 000 000 000$, $1 ≤ K ≤ 1 000 000$.
* Ambii jucători joacă optim ceea ce înseamnă că nu fac greşeli, anticipează mişcările adversarului, iar dacă există o strategie de mişcări care să-i conducă spre câştig atunci o vor folosi.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte.
* Exemplele vor reprezenta teste în valoare de $10$ ("puncte din oficiu") şi vor fi cu feedback.

* $... ≤ ... ≤ ...$

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

| 2
3 5 5
88 200 200
| 5
320
|
| 2
3 5 3
88 200 56
| 7
680

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

|
h3. Explicaţie

h4. Primul exemplu
 
Pentru primul joc, gridul are dimensiunile $N=3, M=5$. Un jucător poate extinde figura cu maxim $K=5$ linii sau coloane. Poziţiile care îi asigură lui Bulănel strategie de câştig sunt $(1;2), (1;4), (2;3), (3;2), (3;4)$.
Pentru al doilea joc, gridul are dimensiunile $N=88, M=200$. Un jucător poate extinde figura cu maxim $200$ de linii sau coloane. Sunt $320$ de poziţii care conduc la câştig.
 
h4. Al doilea exemplu
 
Pentru primul joc, gridul are dimensiunile $N=3, M=5$. Un jucător poate extinde figura cu maxim $K=3$ linii sau coloane. Poziţiile care îi asigură lui Bulănel strategie de câştig sunt $(1;2), (1;4), (2;1), (2;3), (2;5), (3;2), (3;4)$.
Pentru al doilea joc, gridul are dimensiunile $N=88, M=200$. Un jucător poate extinde figura cu maxim $56$ de linii sau coloane. Sunt $680$ de poziţii care conduc la câştig.

...

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