Jesteś ponownie sędzią! Konkurs, który sędziujesz, zawiera następujące zadanie:

„Masz jeden triomino w kształcie litery L każdego z $\frac{4^n-1}{3}$ różnych kolorów. Wyłóż siatkę $2^n$ na $2^n$ przy użyciu każdego z tych triomin w taki sposób, aby pozostało dokładnie jedno puste pole, a wszystkie pozostałe pola były pokryte dokładnie przez jeden kwadrat takiego triomina. Wszystkie triomina muszą zostać użyte”.

Twój zespół ma napisać sprawdzarkę dla tego zadania. Walidacja wartości wejściowych i formatu już się odbyła. Otrzymasz rzekome pokrycie siatki $2^n$ na $2^n$, gdzie każde pole w siatce jest albo $0$, albo liczbą całkowitą dodatnią od $1$ do $\frac{4^n-1}{3}$, reprezentującą jeden z kolorów. Określ, czy jest to rzeczywiście pokrycie siatki za pomocą $\frac{4^n-1}{3}$ unikalnych triomin i pojedynczego pustego pola.

Triomina w kształcie litery L wyglądają następująco:

Wejście

Pierwsza linia wejścia zawiera pojedynczą liczbę całkowitą $n$ ($1 \le n \le 10$), która jest wartością $n$ z opisu.

Każda z kolejnych $2^n$ linii zawiera $2^n$ liczb całkowitych $x$ ($0 \le x \le \frac{4^n-1}{3}$), gdzie $0$ reprezentuje puste pole, a każda liczba dodatnia jest unikalnym identyfikatorem triomina.

Wyjście

Wypisz pojedynczą liczbę całkowitą, która wynosi $1$, jeśli dana siatka jest pokryta $\frac{4^n-1}{3}$ unikalnymi triominami i pojedynczym pustym polem. W przeciwnym razie wypisz $0$.

Przykład

Wejście 1

2
1 1 2 2
1 3 3 2
4 4 3 5
4 0 5 5

Wyjście 1

1

Wejście 2

1
1 1
1 1

Wyjście 2

0