你又擔任裁判了！你所評測的比賽包含以下題目：

「你有 $\frac{4^n-1}{3}$ 種不同顏色的 L 型三格骨牌（triomino）各一個。請使用這些三格骨牌鋪滿一個 $2^n \times 2^n$ 的網格，使得網格中恰好有一個空格，且所有其他方格都被這些三格骨牌中的恰好一個方格所覆蓋。所有三格骨牌都必須被使用。」

你的團隊需要為此題目編寫一個檢查器。輸入數值與格式的驗證已經完成。你將會得到一個 $2^n \times 2^n$ 網格的鋪設結果，其中網格中的每個方格要麼是 $0$，要麼是 $1$ 到 $\frac{4^n-1}{3}$ 之間的一個正整數，代表其中一種顏色。請判斷它是否確實是由 $\frac{4^n-1}{3}$ 個獨特的三格骨牌和一個單一空格所組成的網格覆蓋。

L 型三格骨牌的形狀如下：

輸入格式

第一行包含一個整數 $n$ ($1 \le n \le 10$)，即題目敘述中的 $n$。

接下來的 $2^n$ 行，每行包含 $2^n$ 個整數 $x$ ($0 \le x \le \frac{4^n-1}{3}$)，其中 $0$ 代表空格，任何正整數代表一個三格骨牌的唯一識別碼。

輸出格式

輸出一個整數，若給定的網格是由 $\frac{4^n-1}{3}$ 個獨特的三格骨牌和一個單一空格所覆蓋，則輸出 $1$。否則，輸出 $0$。

範例

輸入 1

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

輸出 1

1

輸入 2

1
1 1
1 1

輸出 2

0