\(N × N\)개의 방으로 이루어진 정사각형 모양의 건물의 왼쪽 위 꼭짓점에 위치한 방에서 유독가스가 유출되었다. 이를 알아챈 철수는 건물의 환기 시스템을 작동하였다. 이제부터 각 방에는 한 가지 방향으로 바람이 불기 시작하였고 유독가스는 이 바람을 타고 위치한 방의 바람의 방향대로 한 칸씩 이동한다.

각 방의 바람의 방향이 숫자로 주어지며 숫자에 따른 방향은 다음과 같다.

• 0:↑(윗쪽)
• 1:↓(아랫쪽)
• 2:←(왼쪽)
• 3:→(오른쪽)

유독가스가 \(N × N\) 격자 밖으로 나가면 환기가 완료된 것으로 한다. 각 바람을 타고 유독가스가 이동했을 때 환기가 완료될 수 있는 지 알아보자.

입력 설명

첫째 줄에 \(N( 1 \le N \le 100 )\) 이 주어진다. 둘째 줄부터 \(N\)줄에 걸쳐 \(N\)개의 바람 방향의 정보가 주어진다.

출력 설명

환기가 완료될 수 있으면 \(1\), 아니면 \(0\)을 출력하시오.

예제 입력 1

3
0 0 0
1 1 1
2 2 2

예제 출력 1

1

예제 입력 2

2
3 1
0 2

예제 출력 2

0