Andrei a învățat un joc matematic interesant care vrea sa îl arate lui Mihai. Jocul începe cu n grămezi de pietre. Fiecare jucător aflat la mutare poate lua pietre dintr-o singură grămadă. Numărul pietrelor luate poate fi 1 sau un număr prim. Jucătorii mută alternativ, iar câștigătorul este cel care ia ultima piatră.
    Andrei se oferă să îl lase pe Mihai să facă prima mutare, dar Mihai știe că Andrei a învățat deja strategia jocului, așa că dorește să afle dacă are sau nu o strategie sigură de câștig. Băieții joacă câte 10 jocuri consecutiv. Sarcina voastră este să îl ajutați pe Mihai cu răspunsul exact pentru fiecare dintre cele 10 configurații.


Fișierul de intrare GAME.IN conține zece linii. Primul număr de pe o astfel de linie reprezintă numărul n al grămezilor, iar în continuare se află n numere care reprezintă numărul pietrelor din fiecare grămadă. Numerele de pe o linie vor fi separate prin spații.

Fișierul de ieșire GAME.OUT va conține câte o linie pentru fiecare dintre configurațiile din fișierul de intrare (în aceeași ordine). Valoarea de pe o linie va fi 1 dacă Mihai are o strategie sigură de câștig pentru configurația corespunzătoare și 0 în caz contrar.

  • 1 <= n <= 1000;
  • numărul total al pietrelor nu va depăși 2000000000 pentru o configurație.


  • GAME.IN
    2 2 1
    3 7 7 7
    1 1000
    2 5 5
    4 3 3 3 3
    2 2 1
    3 7 7 7
    1 1000
    2 5 5
    4 3 3 3 3

    GAME.OUT
    1
    1
    1
    0
    0
    1
    1
    1
    0
    0

    Pentru prima configurație Mihai va lua o piatră din prima grămadă. Apoi, Andrei va lua o piatră din una dintre cele două grămezi,iar Mihai va lua piatra din cealaltă grămadă și va câștiga.
        Pentru cea de-a doua configurație Mihai va lua toate cele șapte pietre din una dintre grămezi. Apoi, Andrei va lua un număr de pietre dintr-una dintre grămezile rămase, iar Mihai va lua același număr de pietre din cealaltă grămadă rămasă. Procesul va continua până în momentul în care nu va mai rămâne nici o piatră. Ultima mutare va fi efectuată cu siguranță de către Mihai.