Little Jhool is a very lenient teaching assistant in his college. He doesn't like cutting the marks of students, so obviously, every student in his tutorial loves him. Specially, the girls. They're crazy about him.
But anyway, the teacher has got to know about the leniency of Jhool while giving marks, so this time in exam, he decides to give a different exam paper to every single student to check how well have the students been taught by Jhool. Now, Little Jhool knows the strong and weak topics of every single student, so he wants to maximize the total marks obtained by students in his tutorial.
You are given the number of students in Jhool's tutorial, denoted by n - n also being the number of different exam papers - that is, one for every student. Every student will get only one exam paper to solve. You are further given a matrix, (n x n) denoting the marks every student will get if he attempts a particular exam paper. You've to help Jhool figure out a way by which he could maximize the total score obtained by his entire class.
Input:
First line contains number of test cases T. The second line contains an integer, denoting n, followed by a n X n matrix - denoting the respective scores of every student in that respective exam.
Output:
Find the TOTAL maximum score obtained by all the students combined.
Constraints:
1<=T<=20
1<=N<=100
1<=Aij<=1000
There are 3 students, and 3 exam papers. Let's denote the matrix by M. The first row contains the scores the first student would obtain if he gave the exam papers. The second row contains the scores for the second student, and likewise the third row. We can clearly see that to MAXIMIZE THE TOTAL SCORE OF THE ENTIRE CLASS, we should ask the third student to give the third paper, the second student to give the second paper, and the first student to give the first paper - thus making the total score equal to ( 9 + 5 + 1 == 15).
