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

const int N  = 5e3+2, inf = 5e17 ;
int a[N][N] , dp1[N][N] , dp2[N][N];
void solve()
  {
     int n , m , i , j ,k ,l ;
      cin >> n ;
      
      for(int i = 0 ; i <= n + 1 ; i++) for(int j = 0 ; j <= n + 1 ;j++)a[i][j] = dp1[i][j] = dp2[i][j] = -inf;
      int ans = -inf ;
      for(int i = 1 ; i <= n ; i++)
         for(int j = 1 ; j <= n ; j++)
            {
               cin >> a[i][j] ;
               int curr =  max(dp1[i-1][j] , dp1[i][j-1]);
               dp1[i][j] = max(a[i][j] + i + j ,curr);
               ans = max( ans , curr + a[i][j] - i - j);
            }
    for(int i = 1 ; i <= n ; i++)
      for(int j = n ; j >= 1 ; j-- )
          {
              int curr = max(dp2[i-1][j] , dp2[i][j+1]);
              dp2[i][j] = max(a[i][j] + i - j , curr);
              ans = max( ans , curr + a[i][j] - i + j);
          }
    cout << ans <<"\n";
  }
signed main()
 {

  int testCases ;
  cin >> testCases ;

  while(testCases--)solve();


 return 0 ;
 }