The Happy Allocation

The panel behind the BTP allocation process has decided to go one step ahead in search for an optimal algorithm for the allocation of BTP topics to students. The panel decides to collect students' preferences of topics as ratings on a scale of 1-5. After having collected such preference ratings, the panel would allocate topics to students in a manner such that every student is allocated a unique topic and the allocation gives a maximum cumulative happiness (CH) score.

Given a list of N topics and a list of N students, an allocation of topics to students is given a happiness score as follows:

cumulative happiness (CH) = [sum over (i,j)] (p(ij)*X(ij)) where p(ij) is the preference rating of student i for topic j and X(ij) is defined as follows:
X(ij) = 1 if topic j is assigned to student i
= 0 otherwise

You need to help the panel get an allocation of topics to students such that the alloation has the maximum cumulative happiness (CH) score.

Input:
The first line of input contains the T - the number of test cases with the subsequent lines containing the description of each test case. The first line of each test case contains the number N. Then N lines follow each consisting of N integers denoting the preference scores of the topics corresponding to each student.

Output:
For each test case, the cumulative happiness score (CH) of the allocation.

Constraints:
1 ≤ T ≤ 5
1 ≤ N ≤ 150