문제

구름 심시티를 하고 있는 플레이어는 한 변의 길이가 인 정사각형 모양의 마을 을 만들고 있다. 번째 행, 번째 열에 해당하는 칸에는 숫자 가 적혀 있다. 는  또는  중 하나이며, 각 숫자가 의미하는 바는 아래와 같다.

• 이면 아무것도 없는 칸이다.
• 이면 집이 있는 칸이다.

마을에 있는 집에 전력을 공급하기 위해선 그 집에 발전기를 설치하거나, 상하좌우로 인접한 집 중 하나가 전력을 공급받고 있으면 된다. 플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 구해보자.

입력

첫째 줄에 마을의 크기 이 주어진다.
다음 개의 줄에는 마을의 상태를 나타내는 개의 숫자가 공백을 두고 주어진다. 번째 줄에서 번째로 주어지는 값이 에 해당한다.

• 
• 는  또는 이다.
• 입력에서 주어지는 모든 수는 정수이다.

출력

플레이어가 모든 집에 전력을 공급하기 위해서 설치해야 할 발전기의 최소 개수를 출력한다.