32211번 - 아이보리와 함께 푸는 스도쿠

문제

$n^2 \times n^2$ 스도쿠는 $n^2 \times n^2$ 격자판에 주어진 규칙에 따라 수를 채워 넣는 게임이다. 격자판을 채우는 규칙은 다음과 같다.

• 게임 시작 전, 격자판의 일부 칸에는 1ドル$ 이상 $n^2$ 이하의 정수가 하나 쓰여있다. 이 수는 바꿀 수 없다.
• 각각의 가로 행과 세로 열에는 1ドル$부터 $n^2$까지의 정수가 하나씩 쓰여있어야 한다.
• $n^2 \times n^2$ 격자판을 겹치지 않는 $n^2$개의 $n \times n$ 격자판으로 나누었을 때, 각 격자판에도 1ドル$부터 $n^2$까지의 정수가 하나씩 들어있어야 한다.

어른보리는 아이보리에게 다음과 같이 스도쿠 문제를 내려고 한다.

1. 어른보리는 두 개의 $n^2 \times n^2$ 격자판을 준비한다. 어른보리만 볼 수 있는 첫 번째 $n^2 \times n^2$ 격자판은 모든 칸이 스도쿠 규칙에 맞게 수가 쓰여있다. 두 번째 격자판은 어른보리와 아이보리 모두가 볼 수 있으며, 처음에는 비어있다.
2. 어른보리는 행 번호가 증가하는 순서대로, 같은 행 안에서는 열 번호가 증가하는 순서대로 두 번째 격자판을 첫 번째 격자판과 동일하게 채워나간다.
3. 어른보리가 두 번째 격자판에 칸을 하나씩 채울 때마다 아이보리는 스도쿠 규칙에 맞게 수를 채우는 방법이 유일한지 확인하고, 유일하다면 스도쿠 문제를 해결한다.

어른보리가 몇 개의 칸을 채워 넣었을 때 아이보리는 스도쿠 문제를 해결할 수 있을까?

입력

첫째 줄에 정수 $n$이 주어진다. $(2 \le n \le 40)$

다음 $n^2$개의 각 줄에는 $n^2$개의 수가 공백으로 구분되어 주어진다. $i$번째 줄의 $j$번째 수는 어른보리가 자신만 볼 수 있는 $n^2 \times n^2$ 격자판의 $i$번째 행 $j$번째 열에 써넣은 수이다. 주어진 수가 $n^2 \times n^2$ 스도쿠의 규칙을 만족함이 보장된다.

출력

아이보리가 $n^2 \times n^2$ 스도쿠 문제를 해결하는 시점에 어른보리가 두 번째 격자판에 채워 넣은 칸의 개수를 출력한다.

제한

힌트