あなたは再び審査員となりました！あなたが審査しているコンテストには、以下の問題が含まれています。

「あなたは、$\frac{4^n-1}{3}$ 種類の異なる色のL字型トロミノをそれぞれ1つずつ持っています。$2^n \times 2^n$ のグリッドを、これらのトロミノをすべて使用してタイル張りしてください。ただし、空のマスがちょうど1つ存在し、それ以外のすべてのマスは、いずれかのトロミノのちょうど1つのマスによって覆われている必要があります。すべてのトロミノを使用しなければなりません。」

あなたのチームは、この問題のチェッカーを作成することになりました。入力値と形式の検証はすでに完了しています。あなたは、$2^n \times 2^n$ のグリッドのタイル張りの結果を与えられます。グリッドの各マスは、$0$ または $1$ から $\frac{4^n-1}{3}$ までの正の整数であり、それぞれ空のマスまたは色の識別子を表しています。これが実際に $\frac{4^n-1}{3}$ 個のユニークなトロミノと1つの空きマスによるグリッドの被覆になっているかどうかを判定してください。

L字型トロミノは以下の形状をしています。

入力

入力の最初の行には、問題文中の $n$ を表す単一の整数 $n$ ($1 \le n \le 10$) が含まれます。 続く $2^n$ 行の各行には、$2^n$ 個の整数 $x$ ($0 \le x \le \frac{4^n-1}{3}$) が含まれます。ここで $0$ は空のマスを表し、正の数はトロミノのユニークな識別子を表します。

出力

与えられたグリッドが $\frac{4^n-1}{3}$ 個のユニークなトロミノと1つの空きマスで覆われている場合は $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