CODE

#include<bits/stdc++.h>
using namespace std;

int a[105][105],cu[105][105];
int main()
{
    int i,j,k,n,m,d,test;
    cin>>test;
    getchar();
    getchar();
    while(test--)
    {
        i=0;
        while(1)
        {
            i++;
            string s;
            getline(cin,s);
            if(s=="") break;
            n=s.size();
            for(j=0;j<n;j++)
            {
                if(s[j]=='0') a[i][j+1]=-100001;
                else a[i][j+1]=1;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                cu[i][j]=cu[i][j-1]+a[j][i];
        }
        long long max_sum=0,sum;
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                sum=0;
                for(k=1;k<=n;k++)
                {
                    sum=sum+cu[k][j]-cu[k][i-1];
                    if(sum<0) sum=0;
                    max_sum=max(sum,max_sum);
                }
            }
        }


        long long final_max_sum=max_sum;
        max_sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(a[i][j]==0) a[i][j]=1;
                else a[i][j]=-100001;
            }
        }
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
                cu[i][j]=cu[i][j-1]+a[j][i];
        }
        for(i=1;i<=n;i++)
        {
            for(j=i;j<=n;j++)
            {
                sum=0;
                for(k=1;k<=n;k++)
                {
                    sum=sum+cu[k][j]-cu[k][i-1];
                    if(sum<0) sum=0;
                    max_sum=max(sum,max_sum);
                }
            }
        }
        final_max_sum=max(max_sum,final_max_sum);
        cout<<final_max_sum<<endl;
        if(test) puts("");
    }
    return 0;
}