#include <bits/stdc++.h>
using namespace std;
int dp[1005][1005];
int main()
{
    int t,m,i,j,n,w;
    scanf("%d",&t);
    for(w=1;w<=t;w++)
    {
        scanf("%d",&n);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                int nr;
                scanf("%d",&nr);
                dp[i][j]=dp[i-1][j]+nr;
            }
        }
    int summax=-1000000;
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++)
    {
        int sum[1005];
        sum[0]=0;
        for(t=1;t<=n;t++)
            sum[t]=sum[t-1]+dp[j][t]-dp[i-1][t];
        summax=max(summax,sum[1]);
        int sum1=sum[1];
        for(t=2;t<=n;t++)
        {
            summax=max(summax,sum1);
            if(sum1<=0)
            {
                sum1=sum[t];
                summax=max(summax,sum1);
            }
            else
            {
                sum1+=sum[t];
                summax=max(summax,sum1);
            }
        }
    }
    printf("%d\n",summax);
    }
    return 0;
}