서양 장기인 체스에는 대각선 방향으로 움직이는 비숍이 있다. 체스판 위에 놓인 두 비숍이 같은 대각선 위에 있다면, 두 비숍은 서로를 잡을 수 있다.

체스판에는 비숍을 놓을 수 있는 칸과 놓을 수 없는 칸이 있다. 비숍을 놓을 수 없는 칸에도 비숍을 놓을 수는 없지만, 비숍은 그 칸을 지나서 이동할 수 있다.

정사각형 체스판의 크기와 각 칸에 비숍을 놓을 수 있는지에 대한 정보가 주어진다. 서로를 잡을 수 없도록 체스판 위에 놓을 수 있는 비숍의 최대 개수를 구하시오.

입력

첫째 줄에 체스판의 크기 \(N\)이 주어진다.

둘째 줄부터 \(N\)개의 줄에 체스판의 각 칸에 비숍을 놓을 수 있는지에 대한 정보가 주어진다. 각 줄에는 \(N\)개의 정수가 공백으로 구분되어 주어진다.

비숍을 놓을 수 있는 칸은 \(1\), 놓을 수 없는 칸은 \(0\)으로 주어진다.

출력

서로를 잡을 수 없도록 놓을 수 있는 비숍의 최대 개수를 출력한다.

제한 사항

• \(1 \le N \le 10\)

예제 입력 1

5
1 1 0 1 1
0 1 0 0 0
0 0 0 0 0
1 0 0 1 1
1 1 0 1 1

예제 출력 1

7