#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
#define int long long
const int N = 1e6 + 10;
const int inf = 1e15;
const int mod = 998244353;

inline void solve(){

    int n;cin >> n;
    vector<vector<int>> v(n, vector<int>(n));

    for(auto &x : v) for(auto &y : x) cin >> y;


    int ans = 0;

    // sum[i][mask] : sum of row i, and mask columns
    // for row i and i + 1, i need to check same column and adjacent columns with adjacent rows
    // but then i need to find the counter mask of this current mask which is easy and iterate on the
    // maximal subset of countermask which i dont like
    // masks are common, they dont care about there position so i can find the subset of masks
    // which are compatible with each other
    // again the number of valid masks change everything




    auto valid = [&](int mask){
        return (mask & (mask << 1)) == 0;
    };

    vector<int> good;

    for(int mask = 0;mask < (1 << n);mask += 1){
        if(valid(mask)){
            good.push_back(mask);
        }
    }

    // cout << good.size() << ' ';

    int m = good.size();

    vector<vector<int>> g(m);

    for(int i = 0;i < m;i += 1){
        for(int j = i + 1;j < m;j += 1){
            int up = good[i], down = good[j];

            if((up & down) > 0){
                continue;
            }

            if(((up << 1) & down) > 0 || ((up >> 1) & down) > 0){
                continue;
            }

            g[i].push_back(j);
            g[j].push_back(i);

        }
    }

    vector<vector<int>> sum(n, vector<int>(m, -inf));

    for(int i = 0;i < n;i += 1){
        for(int k = 0;k < m;k += 1){
            int cur = 0;
            int mask = good[k];

            for(int j = 0;j < n;j += 1){
                if(mask >> j & 1){
                    cur += v[i][j];
                }
            }

            sum[i][k] = cur;
        }
    }

    vector<int> dp(m), ndp(m);

    for(int i = 0;i < m;i += 1){
        dp[i] = sum[0][i];
    }

    for(int i = 1;i < n;i += 1){

        ndp.assign(m, -inf);

        for(int j = 0;j < m;j += 1){
            if(dp[j] == -inf) continue;

            for(auto &x : g[j]){
                ndp[x] = max(ndp[x], dp[j] + sum[i][x]);
            }
        }

        dp = ndp;
    }

    cout << *max_element(dp.begin(), dp.end());

}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    cin >> t;
    while(t--){
        solve();
        cout << '\n';
    }
    return 0;
}