1. 

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 836 - Largest Submatrix
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=10&page=show_problem&problem=777
*
* @author Evgeni Pavlidis
* @version 1.0, 06/05/2010
*
* Method : Kadane - Max substring
* Status : Accepted
* Runtime: 0.112
*/

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

class Main {

private static String[] m = new String[26];

public static void main(String...args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int testCases = Integer.parseInt(reader.readLine());

int[][] rowSum = new int[27][27];
int n, sum = 0, max;

for(int tc = 0; tc < testCases; tc++)
{
if(tc > 0)
System.out.println();

// read input
reader.readLine();
m[0] = reader.readLine();
n = m[0].length();
for(int r = 1; r < n; r++)
m[r] = reader.readLine();


// accumulate row sums
for(int r = 0; r < n; r++, sum = 0)
for(int c = 0; c < n; c++)
rowSum[r][c+1] = sum = sum + (m[r].charAt(c) == '0'? -1000: 1);


// find max substring (submatrix)
max = 0;
for(int c1 = 1; c1 <= n; c1++)
for(int c2 = c1; c2 <= n; c2++, sum = 0)
for(int r = 0; r < n; r++)
{
sum += rowSum[r][c2] - rowSum[r][c1-1];

if(sum < 0)
sum = 0;

if(sum > max)
max = sum;
}

System.out.println(max);
}
}
}