비숍

체스의 비숍은 대각선 방향으로 원하는 만큼 이동할 수 있고, 같은 대각선 위에 있는 다른 말을 잡을 수 있다. 아래 그림에서 B 위치에 있는 비숍은 O로 표시된 칸의 말을 잡을 수 있다.

<그림 1>

정사각형 체스판의 일부 칸에는 비숍을 놓을 수 없다. 아래 그림에서 색칠된 칸이 그런 칸이다. 비숍을 놓을 수 없는 칸에는 비숍을 둘 수 없지만, 비숍이 대각선으로 이동할 때 그 칸을 지나갈 수는 있다.

<그림 2>

서로가 서로를 잡을 수 없도록 비숍을 놓으면, 위와 같은 체스판에서는 아래 그림처럼 최대 7개를 놓을 수 있다.

<그림 3>

체스판의 크기는 한 변에 있는 칸의 개수이다. 체스판의 크기와 각 칸에 비숍을 놓을 수 있는지 여부가 주어질 때, 서로 공격하지 않도록 놓을 수 있는 비숍의 최대 개수를 구하라.

첫째 줄에 체스판의 크기 N이 주어진다. N은 10 이하의 자연수이다.

다음 N개의 줄에는 체스판의 상태가 한 줄씩 주어진다. 각 줄에는 N개의 정수가 공백으로 구분되어 주어진다. 1은 비숍을 놓을 수 있는 칸, 0은 놓을 수 없는 칸을 의미한다.

첫째 줄에 서로 공격하지 않도록 놓을 수 있는 비숍의 최대 개수를 출력한다.