joc

Gică şi Petrică locuiesc în Oraşul Vesel. Acolo există o reţea stradală care conţine doar străzi cu sens unic iar pentru a te deplasa între două intersecţii trebuie să plăteşti o taxă specifică fiecărei intersecţii şi fiecărei străzi prin care treci (inclusiv intersecţia din care pleci şi intersecţia în care ajungi). Aceste taxe nu deranjează însă pe nimeni, deoarece sunt valori monetare naturale între 0 şi 10. Pe cei doi nu îi interesează harta propriu-zisă a Oraşului, însă au găsit tabelul sumelor minime pe care trebuie să le plătească pentru a se plimba între oricare două intersecţii şi s-au gândit să-l folosească pentru a juca un joc interesant (Această matrice conţine numai valori finite).

Astfel, având matricea A în care A[i, j] reprezintă costul minim pentru a ajunge din intersecţia i în intersecţia j (A[i, i] este taxa care trebuie plătită în nodul i), fiecare dintre cei doi mută alternativ, după cum urmează: jucătorul aflat la mutare îşi alege un număr natural strict pozitiv k, şi scade k din toate elementele unei linii sau coloane ale matricei, cu condiţia ca toate elementele matricei să rămână nenegative. Gică mută primul, iar jucatorul care, atunci când îi vine rândul, nu mai poate efectua o mutare corectă, pierde. Se consideră că cei doi prieteni joacă perfect, însemnând că dacă unul dintre ei are la un moment dat o strategie de câştig indiferent de mutările adversarului, nu va efectua o mutare care să ducă la pierderea oricărei strategii de câştig.

Cerinţă

Dându-se matricea A cu semnificaţia din enunţ, aflaţi care dintre cei doi este câştigătorul jocului.

Date de intrare

Fişierul joc.in conţine între 1 şi 20 de seturi de date de intrare. Pe prima linie a fiecărui set se află un număr natural pozitiv N reprezentând dimensiunile matricei A, iar pe următoarele N linii se află câte N numere naturale, reprezentând elementele matricei A. N = 0 marchează sfârşitul seturilor de date ce compun fişierul de intrare.

Date de ieşire

Fişierul de ieşire joc.out va conţine un număr de linii egal cu numărul de seturi de date. Pe fiecare dintre aceste linii se află una dintre valorile: 1 în cazul în care jocul respectiv este câştigat de Gică, 2 în cazul în care jocul respectiv este câştigat de Petrică.

Restricţii

• 1 ≤ numărul testelor ≤ 20
• 2 ≤ N ≤ 100
• Rezolvarea corectă a testelor ce conţin cel mult 10 seturi de date cu N ≤ 5 garantează obţinerea a 50% din punctaj.

Exemplu

joc.in

2
8 25
25 9
2
3 8
9 3
0

joc.out

1
2