#include "bits/stdc++.h"
using namespace std;
#define Lemme_55555555555555555 ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

#define ll  long long
#define mem(arr, val) memset(arr,val,sizeof(arr))
#define sz(s) (int) (s.size())
#define all(vect) vect.begin(), vect.end()
//freopen("Input.txt", "r", stdin); freopen("Output.txt", "w", stdout);
int n,arr[305][305],B,W;
ll dp[305][305],vid,vis[305][305];
ll rec(int i,int take) {
    if (i == n + 1) {
        if (take == B)return 0;
        return -1e16;
    }
    ll &ret = dp[i][take];
    if (vis[i][take] == vid)return ret;
    vis[i][take] = vid;
    int posw = i - take;
    ret = rec(i + 1, take) + arr[i][posw];
    if (take < B)
        ret = max(ret, rec(i + 1, take + 1) + arr[i][W + take + 1]);
    return ret;
}
int main() {
    Lemme_55555555555555555;
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        for (int g = 1; g <= n; g++)
            for (int i = 1; i <= n; i++)cin >> arr[g][i];

        ll mx = LLONG_MIN;
        W = n, B = 0;
        while (B < n) {
            vid++;
            mx = max(mx, rec(1, 0));
            W--, B++;
        }
        cout << mx << "\n";
    }
}