#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int ar[100][100];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cin >> ar[i][j];
}
}
vector<vector<int> > matrix;
vector<int> temp1, temp2;
temp1.push_back(ar[0][0]);
for (int i = 1; i < n - 1; ++i) {
temp1.push_back(ar[i][i]);
temp2.push_back(ar[i][i]);
}
temp2.push_back(ar[n - 1][n - 1]);
matrix.push_back(temp1);
matrix.push_back(temp2);
/*
for (int i = 0; i < n; ++i) {
temp1.push_back(ar[i][i]);
}
matrix.push_back(temp1);
*/
temp1.clear();
temp2.clear();
int j = 0;
for (int i = 1; i < n; ++i) {
j = 0;
int t = i;
while (i < n && j < n) {
temp1.push_back(ar[i][j]);
temp2.push_back(ar[j][i]);
i++;
j++;
}
matrix.push_back(temp1);
matrix.push_back(temp2);
temp1.clear();
temp2.clear();
i = t;
}
/* for (vector<int> temp: matrix) {
for (int i : temp)
cout << i << ", ";
cout << endl;
}*/
vector<int> sum_ar;
int sum = 0;
int ans = 0;
for (int i = 0; i < matrix.size(); i++) {
sum = 0;
for (int j = 0; j < matrix[i].size(); ++j) {
sum += matrix[i][j];
}
ans = max(ans, sum);
}
cout << ans << endl;
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmludCBtYWluKCkgewoKCiAgICBpbnQgdDsKICAgIGNpbiA+PiB0OwoKICAgIHdoaWxlICh0LS0pIHsKCiAgICAgICAgaW50IG47CiAgICAgICAgY2luID4+IG47CiAgICAgICAgaW50IGFyWzEwMF1bMTAwXTsKCgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbjsgKytqKSB7CiAgICAgICAgICAgICAgICBjaW4gPj4gYXJbaV1bal07CiAgICAgICAgICAgIH0KICAgICAgICB9CgoKICAgICAgICB2ZWN0b3I8dmVjdG9yPGludD4gPiBtYXRyaXg7CgogICAgICAgIHZlY3RvcjxpbnQ+IHRlbXAxLCB0ZW1wMjsKCiAgICAgICAgdGVtcDEucHVzaF9iYWNrKGFyWzBdWzBdKTsKCiAgICAgICAgZm9yIChpbnQgaSA9IDE7IGkgPCBuIC0gMTsgKytpKSB7CiAgICAgICAgICAgIHRlbXAxLnB1c2hfYmFjayhhcltpXVtpXSk7CiAgICAgICAgICAgIHRlbXAyLnB1c2hfYmFjayhhcltpXVtpXSk7CiAgICAgICAgfQogICAgICAgIHRlbXAyLnB1c2hfYmFjayhhcltuIC0gMV1bbiAtIDFdKTsKCiAgICAgICAgbWF0cml4LnB1c2hfYmFjayh0ZW1wMSk7CiAgICAgICAgbWF0cml4LnB1c2hfYmFjayh0ZW1wMik7CgovKgoKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkgewogICAgICAgICAgICB0ZW1wMS5wdXNoX2JhY2soYXJbaV1baV0pOwogICAgICAgIH0KCiAgICAgICAgbWF0cml4LnB1c2hfYmFjayh0ZW1wMSk7CiovCgogICAgICAgIHRlbXAxLmNsZWFyKCk7CiAgICAgICAgdGVtcDIuY2xlYXIoKTsKCiAgICAgICAgaW50IGogPSAwOwoKICAgICAgICBmb3IgKGludCBpID0gMTsgaSA8IG47ICsraSkgewoKICAgICAgICAgICAgaiA9IDA7CgogICAgICAgICAgICBpbnQgdCA9IGk7CgogICAgICAgICAgICB3aGlsZSAoaSA8IG4gJiYgaiA8IG4pIHsKCiAgICAgICAgICAgICAgICB0ZW1wMS5wdXNoX2JhY2soYXJbaV1bal0pOwogICAgICAgICAgICAgICAgdGVtcDIucHVzaF9iYWNrKGFyW2pdW2ldKTsKICAgICAgICAgICAgICAgIGkrKzsKICAgICAgICAgICAgICAgIGorKzsKCiAgICAgICAgICAgIH0KICAgICAgICAgICAgbWF0cml4LnB1c2hfYmFjayh0ZW1wMSk7CiAgICAgICAgICAgIG1hdHJpeC5wdXNoX2JhY2sodGVtcDIpOwogICAgICAgICAgICB0ZW1wMS5jbGVhcigpOwogICAgICAgICAgICB0ZW1wMi5jbGVhcigpOwoKICAgICAgICAgICAgaSA9IHQ7CgogICAgICAgIH0KCiAgICAgICAgLyogZm9yICh2ZWN0b3I8aW50PiB0ZW1wOiBtYXRyaXgpIHsKICAgICAgICAgICAgIGZvciAoaW50IGkgOiB0ZW1wKQogICAgICAgICAgICAgICAgIGNvdXQgPDwgaSA8PCAiLCAiOwogICAgICAgICAgICAgY291dCA8PCBlbmRsOwogICAgICAgICB9Ki8KCgogICAgICAgIHZlY3RvcjxpbnQ+IHN1bV9hcjsKCiAgICAgICAgaW50IHN1bSA9IDA7CiAgICAgICAgaW50IGFucyA9IDA7CgogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbWF0cml4LnNpemUoKTsgaSsrKSB7CgogICAgICAgICAgICBzdW0gPSAwOwoKICAgICAgICAgICAgZm9yIChpbnQgaiA9IDA7IGogPCBtYXRyaXhbaV0uc2l6ZSgpOyArK2opIHsKCiAgICAgICAgICAgICAgICBzdW0gKz0gbWF0cml4W2ldW2pdOwoKICAgICAgICAgICAgfQoKICAgICAgICAgICAgYW5zID0gbWF4KGFucywgc3VtKTsKICAgICAgICB9CgoKICAgICAgICBjb3V0IDw8IGFucyA8PCBlbmRsOwoKICAgIH0KCgogICAgcmV0dXJuIDA7Cn0=