There are n gifts and n boxes, each box can contain at most one gift. Now you want to pack all the gifts in the boxes such that your profit is as high possible.
The boxes are numbered from 1 to n and the gifts are numbered from 1 to n. You will be given an (n x n) matrix where pij denotes the profit if we put the ith gift into the jth box. Now your task is to pack all the gifts and maximize the profit.
Input
Input starts with an integer T (≤ 100), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 50). Each of the next n lines contains n space separated integers forming the matrix. The values in the matrix lie in the range [0, 1000].
Output
For each case, print the case number and the maximum profit.
Sample
| Sample Input | Sample Output |
|---|---|
2 2 4 3 3 1 3 1 4 5 5 7 6 5 8 8 | Case 1: 6 Case 2: 18 |