你又当裁判了！你正在评判的比赛包含以下题目：

“你有 $\frac{4^n-1}{3}$ 种不同颜色的 L 型三格骨牌各一个。请用这些骨牌铺满一个 $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