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

Şcoala lui Pătraţel organizează meciul anual de fotbal. Cei doi capitani sunt Pătrăţel şi Triunghiuleţ. Ei îşi vor selecta echipele din cele $N$ clase ale şcolii. Selecţia echipelor funcţionează în felul următor:
 
* Pătrăţel şi Triunghiuleţ aleg membrii alternativ, în ture. Pătrăţel începe.
* Într-o tură, pot fi aleşi doar elevi dintr-o singură clasă.
* Într-o tură, vor fi selectaţi cel puţin unul şi cel mult $K$ elevi.
* Într-o tură, se vor selecta cel mult la fel de mulţi elevi ca în tura precedentă.
* Căpitanul care selectează ultimul (sau ultimii) elevi primeşte premiul "Fo(1)tbal".
 
Căpitanilor nu le pasă câţi elevi selectează, şi toţi elevii sunt identici când vine vorba de fotbal. Le pasă doar de premiul "Fo(1)tbal". Presupunând că amândoi au o strategie perfectă, cine câstigă premiul?

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $football2.in$ va conţine mai multe teste, ce descriu scenarii diferite.
Pe prima linie a unui fişier veţi găsi $T$, numărul de teste. Apoi urmează descrierile testelor.
Pe prima linie a unui test veţi găsi $N$ şi $K$.
Pe a doua linie a unui test veţi găsi $N$ numere întregi pozitive, ce reprezintă mărimile claselor din şcoala lui Pătrăţel.
 
h2. Date de iesire
 
In fisierul de iesire $football2.out$ afişaţi răspunsurile pentru cele $T$ teste, pe un singur rând, fără spaţii între ele. Daca Pătrăţel câştigă premiul într-un test, afişaţi $1$; altfel, afişaţi $0$.
 
h2. Restrictii
 
* $T ≤ 100.000$
* Fie $SN$ suma valorilor lui $N$ pentru toate testele dintr-un fişier. Atunci $SN ≤ 100.000$
* $K, mărimea oricărei clase ≤ 1.000.000.000$
* Pentru $26$ de puncte, $K = 1$
* Pentru alte $8$ puncte, $N ≤ 10$, $SN ≤ 100$, $mărimea oricărei clase ≤ 3$.
* Pentru alte $11$ puncte $N ≤ 10$, $mărimea oricărei clase ≤ 5$.
* Pentru alte $8$ puncte, $N = 1$, $K, mărimea oricărei clase ≤ 100$.
* Pentru alte $16$ puncte, $N = 1$
* Pentru alte $16$ puncte $K = 2$
* Pentru alte $7$ puncte, $K$ e putere de $2$

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

h2. Exemple

h2. Date de ieşire
În fişierul de ieşire $football2.out$ ...

table(example). |_. football2.in |_. football2.out |
| 3
3 1
3 1 1
5 2
2 1 1 1 1
1 2
3|111}

h2. Restricţii

h2. Explicatie

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

În primul test sunt 5 elevi în total, şi exact unul va fi selectat la fiecare tură (căci $K = 1$). Astfel, selecţia va dura exact 5 ture, şi ultimul student va fi selectat în tura lui Pătraţel. Astfel Pătrăţel câştigă.

h2. Exemplu
 
table(example). |_. football2.in |_. football2.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

În al doilea test, Pătrăţel poate mai întâi să selecteze doi elevi din prima clasa. Apoi, după încă patru ture în care fiecare capitan selectează câte un elev (căci toate clasele au doar un elev), Pătrăţel câştigă.

h3. Explicaţie

În al treilea test, Pătrăţel poate selecta iniţial un elev.

...

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