// Arup Guha
// 9/25/04
// Solution to COP 3503H Program #1: 
//     Edited C++ solution to COT 5405 Program #2 from Spring 2004 to 
//     work in Java.

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

public class maxsum {

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

    int n, numcases;
    
    BufferedReader fin = new BufferedReader(new FileReader("sum.in"));
    numcases = Integer.parseInt(fin.readLine());

    // Set up loop to read in each case.
    for (int setnum=1; setnum <=numcases; setnum++) {

      n = Integer.parseInt(fin.readLine());
      int[][] box = new int[100][100];

      // Read in all matrix values.
      for (int i=0; i<n; i++) {
        StringTokenizer tok = new StringTokenizer(fin.readLine());
        for (int j=0; j<n; j++) 
          box[i][j] = Integer.parseInt(tok.nextToken());
      }

      // Based on problem description max > -128.
      int max = -128;

      int[][] aux = new int[100][100];

      // Create and initialize auxiliary array.
      for (int a=0; a<n; a++)
        aux[a][0] = box[a][0];

      // Tabulates sum of all elements in the row up to the current index
      // in each space. Thus, aux[3][4] holds the sum of box[3][0],
      // box[3][1], box[3][2], box[3][3] and box[3][4].
      for (int a=0; a<n; a++)
        for (int b=1; b<n; b++)
          aux[a][b] = aux[a][b-1] + box[a][b];

      // Check all boxes that start with column i and end with column j,
      // looping through each possible choice of i and j.    
      for (int i=0; i<n; i++) {
        for (int j=i; j<n; j++) {
          int mcss = maxs(aux, i, j, n);
  
          // Update the MCSS if necessary.
          if (mcss > max)
            max = mcss;
        }
      } 

      // Output the result.
      System.out.println("Test case#"+setnum+": The maximal sum is "+max+".");

    }

    fin.close();
  }

  // Returns the maximum sum of all boxes starting at column i and ending 
  // at column j.
  public static int maxs(int[][] aux, int i, int j, int n) {

    int s;

    if (i>0) {

      // Set s to the sum of the first row of the box from col i to col j.
      s=aux[0][j]-aux[0][i-1];
      int sum = 0;

      // Do the MCSS algorithm using each row sum as a term.
      for (int x=0; x<n; x++) {

        // Add in next row.
        sum += aux[x][j]-aux[x][i-1];

        // Update running sum and maximum as necesary.
        if (sum > s) 
          s = sum;
        if (sum < 0)
          sum = 0;
      }
    } 

    else {

      // Exact same code as above, except for initialization of s and
      // Computation of the sum of each row.
      s=aux[0][j];
      int sum = 0;
    
      for (int x=0; x<n; x++) {
        sum += aux[x][j];
        if (sum > s) 
          s = sum;
        if (sum < 0)
          sum = 0;
      }

    } // end if-else
    return s;

  } // end maxs

}