// Solution to Inspectors
//
// Code copied from "Sofa, So Good" (2012 contest), which was basically 
// just copied from TopCoder:
//   http://community.topcoder.com
//                      /tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
// but changing some variable names and negating all input values to convert 
// maximize to minimize.

import java.util.*;

public class E {
  public static Scanner in;
  public static int n, casenum;
  public static int[][] dist;


  public static int[][] c; // parameter
  public static int matched, maxwt; // # edges and weight of matching
  public static int[] xlabel,ylabel; // labels
  public static int[] xmatch,ymatch; // nbrs in matching
  public static boolean[] s,t; // sets used in augmentation
  public static int[] prev, slack, slackx;

  public static void main(String[] args) {
    in = new Scanner(System.in);
    int m = in.nextInt();
    for(casenum = 1; casenum <= m; casenum++) {
     // Input the problem data:
      n = in.nextInt();
      dist = new int[n][n];
      for (int i = 0; i < n; i++) {
//        Arrays.fill(dist[i], -Integer.MAX_VALUE); // negate to use max matching
        Arrays.fill(dist[i], -10000); // negate to use max matching
      }
      for (int i = 0; i < n-1; i++) {
        for (int j = i+1; j < n; j++) {
          dist[i][j] = dist[j][i] = -in.nextInt(); // negate to use max matching
        }
      }
/* DEBUG:
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    System.out.printf("%11d ",dist[i][j]);
  }
  System.out.println();
}
*/
      c = dist; // rename so I can use copied code!!
      solve();
      System.out.print("Case " + casenum + ": ");
      int sum = 0;
      for (int i = 0; i < n; i++) {
/* DEBUG:
System.out.printf("%d->%d (%d)\n",1+i,1+xmatch[i],-dist[i][xmatch[i]]);
*/
        sum -= dist[i][xmatch[i]];
      }
      System.out.println(sum);
    }
  }

  // Algorithm/code borrowed from:
  // http://community.topcoder.com/
  //           tc?module=Static&d1=tutorials&d2=hungarianAlgorithm
  // For a while I added my own comments to explain to myself what
  // was going on...

  public static void solve() {
    // Initial empty matching:
    maxwt = 0; // max so far (which we negate to get min)
    matched = 0; // number of edges in current matching
    xmatch = new int[n];
    Arrays.fill(xmatch,-1);
    ymatch = new int[n];
    Arrays.fill(ymatch,-1);

    // Initial feasible labeling:
    xlabel = new int[n];
    ylabel = new int[n];
    Arrays.fill(xlabel,0);
    Arrays.fill(ylabel,0); // labels all 0
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        xlabel[i] = Math.max(xlabel[i],c[i][j]); // labels = max edge
    slack = new int[n];
    slackx = new int[n];
    // The hard part:
    augment();
  }

  public static void augment() {
    if (matched==n) return;
    int x, y, root=-1;
    int q[] = new int[n]; // a queue
    int wr=0,rd=0;        // tail and head of queue
    s = new boolean[n];
    t = new boolean[n];
    Arrays.fill(s,false);
    Arrays.fill(t,false);
    prev = new int[n];
    Arrays.fill(prev,-1);

    // Look for an exposed vertex in the equality graph:
    for (x = 0; x < n; x++) {
      if (xmatch[x] == -1) {
        q[wr++] = root = x; // root of alt. tree; queued for BFS
        prev[x] = -2; // no parent in tree since root
        s[x] = true;  // place x in s
        break; // found root of aug tree--done
      }
    }

    // Build alt. path tree. At some point we are going to
    // need to find smallest difference between edge cost
    // and label cost; slack helps us find that and slackx
    // helps us remember where the label changes have to take place.
//    slack = new int[n];
//    slackx = new int[n];
    for (y = 0; y < n; y++) {
      slack[y] = xlabel[root]+ylabel[y]-c[root][y];
      slackx[y] = root;
    }

    while (true) //main cycle
    {
      while (rd < wr) //building tree with bfs cycle
      {
        x = q[rd++]; //current vertex from X part
        for (y = 0; y < n; y++) //iterate through all edges in equality graph
          if (c[x][y] == xlabel[x] + ylabel[y] &&  !t[y])
          {
            if (ymatch[y] == -1) break; //an exposed vertex in Y found, so
                                    //augmenting path exists!
            t[y] = true; //else just add y to T,
            q[wr++] = ymatch[y]; //add vertex ymatch[y], which is matched
                               //with y, to the queue
            add(ymatch[y], x); //add edges (x,y) and (y,ymatch[y]) to the tree
          }
        if (y < n) break; //augmenting path found!
      }
      if (y < n) break; //augmenting path found!
      update(); //augmenting path not found, so improve labeling
      wr = rd = 0;                
      for (y = 0; y < n; y++)        
        //in this cycle we add edges that were added to the equality
        //graph as a result of improving the labeling, we add 
        // edge (slackx[y], y) to the tree if and only if !T[y] 
        // &&  slack[y] == 0, also with this edge we add another one
        // (y, ymatch[y]) or augment the matching, if y was exposed
        if (!t[y] &&  slack[y] == 0)
        {
          if (ymatch[y] == -1) //exposed vertex in Y found - augmenting path exists!
          {
            x = slackx[y];
            break;
          }
          else
          {
            t[y] = true; //else just add y to T,
            if (!s[ymatch[y]])    
            {
              q[wr++] = ymatch[y]; //add vertex ymatch[y], which is matched with
                                   //y, to the queue
              add(ymatch[y], slackx[y]); //and add edges (x,y) and (y,
                                         //ymatch[y]) to the tree
             }
           }
         }
       if (y < n) break; //augmenting path found!
    }

    if (y < n) //we found augmenting path!
    {
       matched++; //increment matching
        //in this cycle we inverse edges along augmenting path
        for (int cx = x, cy = y, ty; cx != -2; cx = prev[cx], cy = ty)
        {
            ty = xmatch[cx];
            ymatch[cy] = cx;
            xmatch[cx] = cy;
        }
        augment(); //recall function, go to step 1 of the algorithm
    }
  }

  public static void update() {
    int x, y, delta = Integer.MAX_VALUE;

    // delta = smallest slack value in the complement of
    // neighborhood of x-nodes in equality graph 
    for (y = 0; y < n; y++) {
      if (!t[y]) delta = Math.min(delta,slack[y]);
    }

    // Apply delta to edges not in equality graph:
    for (x = 0; x < n; x++)
      if (s[x]) xlabel[x] -= delta;
    for (y = 0; y < n; y++)
      if (t[y]) ylabel[y] += delta;
    for (y = 0; y < n; y++)
      if (!t[y]) slack[y] -= delta;
  }

  public static void add(int x, int prevx) {
    s[x] = true;
    prev[x] = prevx;
    for (int y = 0; y < n; y++)
      if (xlabel[x]+ylabel[y] - c[x][y] < slack[y]) {
        slack[y] = xlabel[x]+ylabel[y]-c[x][y];
        slackx[y] = x;
      }
  }
}