당신은 다시 한번 심판이 되었습니다! 당신이 심사하는 대회에는 다음과 같은 문제가 포함되어 있습니다.

"당신은 $\frac{4^n-1}{3}$개의 서로 다른 색상을 가진 L자형 트리오미노를 각각 하나씩 가지고 있습니다. $2^n \times 2^n$ 격자를 이 트리오미노들을 사용하여 채우되, 정확히 하나의 빈 칸이 존재하고 나머지 모든 칸은 정확히 하나의 트리오미노 칸으로 덮여야 합니다. 모든 트리오미노는 반드시 사용되어야 합니다."

당신의 팀은 이 문제에 대한 검사기(checker)를 작성해야 합니다. 입력 값과 형식에 대한 검증은 이미 완료되었습니다. 당신은 $2^n \times 2^n$ 격자에 대한 타일링 결과가 주어지며, 격자의 각 칸은 $0$이거나 $1$부터 $\frac{4^n-1}{3}$ 사이의 양의 정수(색상을 나타냄)입니다. 이것이 실제로 $\frac{4^n-1}{3}$개의 고유한 트리오미노와 하나의 빈 칸으로 격자를 덮은 것인지 확인하십시오.

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$을 출력하고, 그렇지 않다면 $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