#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 ;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgaW50IGxvbmcgbG9uZyAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBOICA9IDVlMysyLCBpbmYgPSA1ZTE3IDsKaW50IGFbTl1bTl0gLCBkcDFbTl1bTl0gLCBkcDJbTl1bTl07CnZvaWQgc29sdmUoKQogIHsKICAgICBpbnQgbiAsIG0gLCBpICwgaiAsayAsbCA7CiAgICAgIGNpbiA+PiBuIDsKICAgICAgCiAgICAgIGZvcihpbnQgaSA9IDAgOyBpIDw9IG4gKyAxIDsgaSsrKSBmb3IoaW50IGogPSAwIDsgaiA8PSBuICsgMSA7aisrKWFbaV1bal0gPSBkcDFbaV1bal0gPSBkcDJbaV1bal0gPSAtaW5mOwogICAgICBpbnQgYW5zID0gLWluZiA7CiAgICAgIGZvcihpbnQgaSA9IDEgOyBpIDw9IG4gOyBpKyspCiAgICAgICAgIGZvcihpbnQgaiA9IDEgOyBqIDw9IG4gOyBqKyspCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgY2luID4+IGFbaV1bal0gOwogICAgICAgICAgICAgICBpbnQgY3VyciA9ICBtYXgoZHAxW2ktMV1bal0gLCBkcDFbaV1bai0xXSk7CiAgICAgICAgICAgICAgIGRwMVtpXVtqXSA9IG1heChhW2ldW2pdICsgaSArIGogLGN1cnIpOwogICAgICAgICAgICAgICBhbnMgPSBtYXgoIGFucyAsIGN1cnIgKyBhW2ldW2pdIC0gaSAtIGopOwogICAgICAgICAgICB9CiAgICBmb3IoaW50IGkgPSAxIDsgaSA8PSBuIDsgaSsrKQogICAgICBmb3IoaW50IGogPSBuIDsgaiA+PSAxIDsgai0tICkKICAgICAgICAgIHsKICAgICAgICAgICAgICBpbnQgY3VyciA9IG1heChkcDJbaS0xXVtqXSAsIGRwMltpXVtqKzFdKTsKICAgICAgICAgICAgICBkcDJbaV1bal0gPSBtYXgoYVtpXVtqXSArIGkgLSBqICwgY3Vycik7CiAgICAgICAgICAgICAgYW5zID0gbWF4KCBhbnMgLCBjdXJyICsgYVtpXVtqXSAtIGkgKyBqKTsKICAgICAgICAgIH0KICAgIGNvdXQgPDwgYW5zIDw8IlxuIjsKICB9CnNpZ25lZCBtYWluKCkKIHsKCiAgaW50IHRlc3RDYXNlcyA7CiAgY2luID4+IHRlc3RDYXNlcyA7CgogIHdoaWxlKHRlc3RDYXNlcy0tKXNvbHZlKCk7CgoKIHJldHVybiAwIDsKIH0=