Server Time: Sat Sep 22, 2018 3:06 am
Welcome ( logout
1222 - Gift Packing
  PDF (English) Statistics Forum
Time Limit: 1 second(s) Memory Limit: 32 MB

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 Input

Output for Sample Input

2

2

4 3

3 1

3

1 4 5

5 7 6

5 8 8

Case 1: 6

Case 2: 18

 


Problem Setter: Jane Alam Jan
Developed and Maintained by
JANE ALAM JAN
Copyright © 2012
LightOJ, Jane Alam Jan