Vestigium

Vestigium은 라틴어로 '흔적'이라는 뜻이다. 이 문제에서는 라틴 방진과 행렬의 대각합을 다룬다.

정사각 행렬의 대각합은 왼쪽 위에서 오른쪽 아래로 이어지는 주대각선에 있는 값들의 합이다.

$N \times N$ 행렬의 각 칸에 서로 다른 $N$개의 값 중 하나가 들어 있고, 같은 행이나 같은 열에 같은 값이 반복되지 않으면 라틴 방진이다. 이 문제에서는 $N$개의 값이 1부터 $N$까지의 정수인 자연 라틴 방진만 다룬다.

1부터 $N$까지의 정수만 담긴 행렬이 주어지면 대각합을 구하고, 자연 라틴 방진인지 확인한다. 자연 라틴 방진인지 여부만 답하는 대신, 같은 값이 반복되는 행의 수와 열의 수를 함께 센다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 행렬의 크기 $N$만 담긴 줄로 시작한다. 그 다음 $N$개의 줄에 걸쳐 $i$번째 줄마다 $N$개의 정수 $M_{i,1}, M_{i,2}, \ldots, M_{i,N}$이 주어진다. $M_{i,j}$는 행렬의 $i$행 $j$열에 있는 정수다.

각 테스트 케이스마다 Case #x: k r c 형식의 한 줄을 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호, $k$는 행렬의 대각합, $r$은 반복되는 원소를 포함한 행의 수, $c$는 반복되는 원소를 포함한 열의 수다.

• $1 \le T \le 100$.
• $2 \le N \le 100$.
• 모든 $i, j$에 대해 $1 \le M_{i,j} \le N$.

예제 #1의 입력은 자연 라틴 방진이므로 반복되는 원소가 있는 행이나 열이 없다. 주대각선의 네 값이 모두 1이므로 대각합은 4다.

예제 #2에서는 모든 행과 모든 열에 반복되는 원소가 있다. 반복되는 원소가 있는 행이나 열은 몇 개의 값이 반복되는지, 몇 번 반복되는지와 상관없이 한 번만 센다. 또한 1부터 $N$까지의 정수 중 일부는 입력에 나타나지 않을 수 있다.

예제 #3에서는 가장 왼쪽 열과 가장 오른쪽 열에 반복되는 원소가 있다.