There were n friends. But some of them had problems with others. So, we can say each person has some dissatisfaction with others. And hence we introduce a new term 'Dissatisfaction Factor' and it is described as follows:

You are given all the dissatisfaction factors as d_ij. d_ij means the dissatisfaction factor according to person i towards j. If the value is negative that means i^th person likes j^th person. Positive value means i^th person hates j^th person. 0 means i^th person is neutral about j^th person. Obviously d_ij can be different from d_ji since i^th person may like j^th person, but j^th person may not like i^th person and vice versa.

Now, if you group some people, the dissatisfaction factor is the summation of all the members' dissatisfaction factors towards other people in the group. You have to group them with minimum dissatisfaction factor. You can make as many groups as you like.

Input starts with an integer T (≤ 100), denoting the number of test cases.

Each case starts with a line containing an integer n (2 ≤ n ≤ 14). Each of the next n lines contains n space separated integers. The j^th integer in the i^th line denotes d_ij. You can assume that -100 ≤ d_ij ≤ 100 and of course d_ii = 0.

For each case, print the case number and the minimum dissatisfaction factor you can make after grouping them.