Vestigium

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

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

$N \times N$ 정사각 행렬에서 각 칸이 N개의 서로 다른 값 중 하나를 포함하고, 어떤 값도 한 행이나 한 열 안에서 반복되지 않으면 이 행렬을 라틴 방진이라고 한다. 이 문제에서는 N개의 값이 1 이상 N 이하의 정수인 "자연 라틴 방진"만 다룬다.

1 이상 N 이하의 정수만 포함하는 행렬이 주어질 때, 행렬의 대각합을 계산하고 이 행렬이 자연 라틴 방진인지 확인하려 한다. 추가 정보를 제공하기 위해, 행렬이 자연 라틴 방진인지 여부만 알려 주는 대신 반복되는 값을 포함하는 행의 수와 열의 수를 계산하라.

제한

테스트 세트 1 (판정 공개)

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. 2 ≤ N ≤ 100. 모든 i, j에 대해 1 ≤ $M_{i,j}$ ≤ N.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 조사할 행렬의 크기인 하나의 정수 N을 포함하는 줄로 시작한다. 그다음 N개의 줄이 주어진다. 이 줄들 중 i번째 줄에는 N개의 정수 $M_{i,1}$, $M_{i,2}$ ..., $M_{i,N}$가 주어진다. $M_{i,j}$는 행렬의 i번째 행과 j번째 열에 있는 정수이다.

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

예제 케이스 #1에서 입력은 자연 라틴 방진이므로 어떤 행이나 열에도 반복되는 원소가 없다. 주대각선에 있는 네 값은 모두 1이고, 따라서 대각합(이 값들의 합)은 4이다.

예제 케이스 #2에서는 모든 행과 열에 반복되는 원소가 있다. 반복되는 원소가 있는 각 행이나 열은 반복되는 원소의 수나 해당 행 또는 열 안에서 반복되는 횟수와 관계없이 단 한 번만 센다는 점에 유의하라. 또한 1 이상 N 이하의 범위에 있는 일부 정수가 입력에 없을 수도 있다는 점에 유의하라.

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