Maximum Happiness Assignment

You are given an \( n \times n \) matrix \( A \) where \( A_{ij} \) represents the happiness that can be achieved by selecting cell \( (i,j) \). Sarah wants to select exactly one element from each row and each column such that the total happiness is maximized.

Your task is to find a permutation \( p \) of \( \{1, 2, \dots, n\} \) that maximizes the sum

[ \sum_{i=1}^{n} A_{i, p(i)} ]

and output the maximum total happiness.

Note: It is guaranteed that the matrix is square. You should solve the problem by reading from standard input and writing to standard output.

inputFormat

The first line contains an integer \( T \) denoting the number of test cases.

For each test case, the first line contains an integer \( n \) denoting the size of the matrix. Each of the next \( n \) lines contains \( n \) space-separated integers representing the rows of the matrix.

outputFormat

For each test case, output a single integer on a new line denoting the maximum total happiness possible by selecting one element from each row and each column.

## sample

3
3
1 2 3
4 5 6
7 8 9
4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
3
2 1 3
1 3 2
3 2 1

15
34
9

</p>