#include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <queue>

 using namespace std;

 #define REP(i,n) for(int i=0; i<(n); i++)

 #define FOR(i,s,t) for(int i=(s); i<=t; i++)

 typedef long long ll;

 const int INF = <<;

 const int N = ;

 int S[N][N],n,_;

 int sum[N];

 void show(){

     FOR(i,,*n){

         FOR(j,,*n)

             printf("%4d",S[i][j]);

         cout<<endl;

     }

 }

 void solve(){

     scanf("%d", &n);

     //矩阵扩大

     FOR(i,,n) FOR(j,,n){

          scanf("%d", &S[i][j]);

          S[i+n][j] = S[i][j];

          S[i][j] += S[i-][j];

          S[i][j+n] = S[i][j];

     }

     FOR(i,n+,*n) FOR(j,,n){

         S[i][j] += S[i-][j];

         S[i][j+n] = S[i][j];

     }

     int ans = -INF;

     FOR(i,,n) FOR(j,i+,i+n){//枚举上下边界，从右往左扫描

          int q[N<<],head=,tail=;

          for(int k = ; k<*n; k++){

              sum[k] =S[j][k] - S[i][k] + sum[k-];

              while(tail>head && sum[k] <= sum[q[tail]]) tail--;//用单调队列优化

              q[++tail] = k;

              while(tail>head && k - q[head+]>n) head++;

              ans  = max(ans , sum[k] - sum[q[head+]]);

          }

     }

     printf("%d\n",ans);

 }

 int main(){

 //    freopen("in.txt","r",stdin);

     scanf("%d", &_);

     while(_--) solve();

     return ;

 }