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

Poveste şi cerinţă...

Tanaka va juca un joc cu prietenul său cel mai bun, Uivlis. Jocul decurge în felul următor:
 
# Fie mulţimea $P = {1} U {p | p e prim}$
# Se dă o matrice de $N x M$, şi un număr natural $K$.
# Tanaka joaca primul
# La tura lui $X$, se vor întâmpla următoarele:
## $X$ selectează o poziţie în matrice.
## $X$ scade din poziţia selectată orice număr din mulţimea $P$, astfel încât rezultatul e nenegativ.
## $X$ selectează un drum de lungime cel mult $K$, care merge doar în dreapta şi în jos, începând de la poziţia selectată în pasii precedenti.
## Pentru toate poziţiile din drum, exceptând poziţia initial selectat, mai întâi $X$ va adauga un număr din $P$, apoi va scădea oricare numar din $P$ din poziţie, astfel încât rezultatul e nenegativ.
# Cel care nu poate face o mutare valida pierde.
 
h2. Cerinţa
 
Cunoscând starea iniţiale ale jocului să se determine cine câştigă, daca ambii jucatori joaca optim.

h2. Date de intrare

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

Fişierul de intrare $tanakagame.in$ conţine pe primul rând numarul de jocuri $T$, urmat de descrierile celor $T$ jocuri.
Pe prima linie corespunzătoare unui test sunt 3 numere $N, M, K$ cu semnificaţia din enunţ.
Urmatoarele $N$ linii ale testului conţin câte $M$ numere şi reprezintă valorile elementelor din matrice.

h2. Date de ieşire

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

Fişierul de ieşire $tanakagame.out$ conţine răspunsurile corespunzătoare jocurilor, fiecare răspuns pe câte o linie. Pentru fiecare joc se va afişa mesajul $Tanaka$ dacă Tanaka căştigă, respectiv $Uivlis$ dacă căştigă Uivlis.

h2. Restricţii

h2. Restricţii şi precizari

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

* $1 ≤ N, M ≤ 50$
* $1 ≤ K ≤ 100$
* $0 ≤ valorile din matrice ≤ 99$
* $1 ≤ T ≤ 40$
* Pentru $10$ puncte, $N = M = K = 1$
* Pentru alte $10$ puncte, $N = 1, M = 2, K = 2$
* Pentru alte $20$ de puncte, $N = 1, K = M$
* Pentru alte $40$ de puncte, $K = 100$

h2. Exemplu

table(example). |_. tanakagame.in |_. tanakagame.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. tanakagame.in |_. tanakagame.out |_. Explicaţii |
| 5
1 1 1
4
1 2 2
72 40
1 1 5
99
3 4 100
56 75 56 29
55 95 87 83
71 98 27 24
3 4 4
95 13 22 1
69 55 99 80
65 70 75 10
| Uivlis
Uivlis
Tanaka
Uivlis
Tanaka
| În primul joc, după mutarea lui Tanaka, singura poziţie
din matrice va conţine fie 1, 2 sau 3. În oricare caz,
Uivlis poate muta astfel încat rezultatul să fie 0, caz în
care Tanaka pierde.
|

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