#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define all(v) v.begin(),v.end()
#define sz(s) (int)(s).size()
#define ll long long
#define ld long double
#define el "\n"
#define PI  3.141592653589793
#define fx(x) fixed<<setprecision(x)
#define F first
#define S second
#define memo(mem, val) memset(mem, val, sizeof(mem))
#define IOS ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);

void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}
const int N=1e5+5;
int n;
ll arr[302][302],dp[302][302][302],vis[302][302][302];
int val,id=1;
ll rec(int c_w,int r,int c_b) {
    if (c_w == val) {
        int x=c_b;
        ll sum=0;
        for (int i = r+1; i <=n ; ++i) {
            sum+=arr[i][x];
            x++;
        }
        return sum;
    }
    ll &ret = dp[c_w][r][c_b];
    if (vis[c_w][r][c_b]==id)return ret;
    vis[c_w][r][c_b]=id;
    for (int i = r + 1; i <= n; ++i) {
        ll x = 0, tmp = c_b;
        for (int j = r + 1; j < i; ++j) {
            x += arr[j][tmp];
            tmp++;
        }
        ret = max(ret, rec(c_w + 1, i, tmp) + x + arr[i][c_w]);
    }
    return ret;
}
void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> arr[i][j];
        }
    }
    memo(dp,-1);
    memo(vis,0);
    ll ans=0;
    for (int i = 1; i <=n ; ++i) {
        id++;
        val=i;
        ans= max(ans, rec(min(i,1),0,i+1));
    }

    cout<<ans;
}
int main() {
    IOS
    File();
    int tc = 1;
    cin >> tc;
    for (int i = 1; i <= tc; ++i) {
        solve();
        if (i < tc) cout << "\n";
    }

    return 0;
}