// Arup Guha
// Written in 2007 during practice before 2007 UCF HS contest.
// Commented 11/4/09

import java.util.*;
import java.io.*;

// Just supports a basic edge class.
class edge implements Comparable {

  // start and end are vertices and weight is the
  // weight of this edge.
  public int start;
  public int end;
  public int weight;

  public edge(int a, int b, int c) {
    start = a;
    end = b;
    weight = c;
  }

  // We want to sort edges by edge weight.
  public int compareTo(Object o) {

    if (o instanceof edge) {
      edge tmp = (edge)o;
      return this.weight - tmp.weight;
    }
    return -1;
  }
}

// Maintains a Disjoint Set.
class dj {

  public int[] values;

  // Initially all nodes are in separate trees.
  public dj(int size) {
    values = new int[size];
    for (int i=0; i<size; i++) values[i] = i;
  }

  // Recursively find a node's root, so really this should
  // be called root and not parent =)
  public int parent(int node) {
    if (node == values[node])
      return node;
    else
      return parent(values[node]);
  }

  // Merges/fuses two trees together. No optimization is done,
  // I automatically make j's tree a child of i's tree.
  public void merge(int i, int j) {
    int a = parent(i);
    int b = parent(j);
    values[b] = a;
  }
}

public class cpu {

  public static void main(String[] args) throws IOException {

    Scanner fin = new Scanner(new File("cpu.in"));

    int numcases = fin.nextInt();
    for (int z=1; z<=numcases; z++) {

	  // This is the largest this array needs to be.
      int size = fin.nextInt();
      edge[] all = new edge[size*(size-1)/2];

      // Read through all of the edges and add them to the edge array.
      int index = 0;
      for (int i=0; i<size; i++) {
        for (int j=0; j<size; j++) {
          int myw = fin.nextInt();
          if (i < j) {
            all[index] = new edge(i,j,myw);
            index++;
          }
        }
      }

      // Sort the edges in order!
      Arrays.sort(all);

      // We'll use this disjoint set for cycle detection.
      dj mine = new dj(size);
      int cnt = 0, ans=0;
      int myindex = 0;

      // Loop until we've added size-1 edges to our MST.
      while (cnt < size-1) {

      	// This is the current edge to consider adding to our MST.
        edge tmp = all[myindex];

        // If it doesn't cause a cycle, add it!
        if (mine.parent(tmp.start) != mine.parent(tmp.end)) {

          // Just update our MST weight.
          ans += tmp.weight;

          // These two vertices's trees must now be connected.
          mine.merge(tmp.start,tmp.end);

          // Add one to our count of edges in our MST.
          cnt++;
        }

        // Go to the next edge to consider.
        myindex++;
      }

      System.out.println("Design "+z+": "+ans+" micrometers");
    }

    fin.close();
  }

}