POLSKI SPOJ

Organizatorzy pewnych bardzo znanych zawodów programistycznych postanowili ułatwić sprawę grupie finalistów i zrezygnować z większości testów wydajnościowych. Wpadli oni na pomysł, że czas spędzony na usuwaniu kolejnych linii tekstu będzie zdecydowanie szybciej płynął jeżeli uczynią z tej czynności grę. W grze tej obowiązują następujące zasady:

1. W grze bierze udział dwóch graczy o numerach 1 i 2, którzy ruszają się na przemian.
2. Grę rozpoczyna gracz z numerem 1.
3. W każdym ruchu gracz może z dowolnie wybranej niepustej linii usunąć dowolną ilość znaków większą od 0.
4. Grę wygrywa ten z graczy, który usunie ostatni znak z ostatniej niepustej linii.

Każdemu z organizatorów bardzo zależy na wygranej, w związku z czym nie pozwolą oni sobie na popełnienie jakiegoś błędu i obydwaj będą wykonywać optymalne ruchy. Twoim zadaniem jest wytypowanie zwycięzcy na podstawie początkowej zawartości pliku czyli ilości linii oraz ilości znaków w każdej linii.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba naturalna Z (1 ≤ Z ≤ 10) określająca ilość zestawów danych. W kolejnych liniach znajdują się zestawy danych.

W pierwszej linii każdego zestawu danych znajduje się jedna liczba całkowita n (1 ≤ n ≤ 10⁵) określająca ilość linii w pliku z testami. W kolejnej linii znajduje się n liczb oddzielonych spacjami. Liczba i-ta w kolejności określa ilość znaków w i-tej linii pliku z testami. Ilość znaków w linii nie przekracza 10⁶.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać cyfrę 1 jeżeli to pierwszy gracz zwycięży albo cyfrę 2 w przeciwnym przypadku.

Przykład

Wejście:

3
1
5
3
1 2 3
3
3 4 5

Wyjście:

1
2
1