Vestigium

Vestigium means 'trace' in Latin. In this problem we work with Latin squares and matrix traces.

The trace of a square matrix is the sum of the values on the main diagonal, which runs from the upper left to the lower right.

An $N \times N$ matrix is a Latin square if each cell contains one of $N$ different values, and no value is repeated within a row or a column. This problem deals only with natural Latin squares, in which the $N$ values are the integers from 1 to $N$.

Given a matrix that contains only integers from 1 to $N$, compute its trace and check whether it is a natural Latin square. Instead of only reporting whether it is one, count the rows and the columns that contain repeated values.

The first line contains the number of test cases $T$. Then $T$ test cases follow. Each test case starts with a line containing a single integer $N$, the size of the matrix. Then $N$ lines follow. The $i$-th of these lines contains $N$ integers $M_{i,1}, M_{i,2}, \ldots, M_{i,N}$, where $M_{i,j}$ is the integer in row $i$ and column $j$.

For each test case, output one line containing Case #x: k r c. Here $x$ is the test case number starting from 1, $k$ is the trace of the matrix, $r$ is the number of rows that contain repeated elements, and $c$ is the number of columns that contain repeated elements.

• $1 \le T \le 100$.
• $2 \le N \le 100$.
• $1 \le M_{i,j} \le N$ for all $i, j$.

In Sample Case #1, the input is a natural Latin square, so no row or column has repeated elements. All four values on the main diagonal are 1, so the trace is 4.

In Sample Case #2, every row and every column has repeated elements. A row or column with repeated elements is counted only once, no matter how many values repeat or how often. Some integers from 1 to $N$ may also be absent from the input.

In Sample Case #3, the leftmost and rightmost columns have repeated elements.