#include <bits/stdc++.h>
#define ll long long
#define PI 3.14159265359
#define DP(x, y) memset(x, y, sizeof x)
#define all(x) x.begin(), x.end()
#define read(x) freopen("x", "r", stdin);
#define write(x) freopen("x", "w", stdout);
using namespace std;
ll gcd(ll a,ll b) { while(b) { ll x = a; a = b; b = x % b; } return a; }
ll lcm(ll a,ll b) { return a / gcd(a, b) * b; }
ll nC2(ll n) { return (n)*(n-1)/2; }
ll summing(ll n) { return (n)*(n+1); }
const int N = 8;
int vis_col[50] = {0};
int vis_row[50] = {0};
int vis_right[50] = {0};
int vis_left[50] = {0};
int MaxNQueens(int col, vector<vector<int>>&grid) {
if (col == N) {
return 0;
}
int maximum = 0;
for (int row=0; row<N; row++) {
if ((vis_row[row] == 0) && (vis_left[col-row+N-1] == 0) && (vis_right[row+col] == 0)) {
vis_row[row] = 1;
vis_left[col-row+N-1] = 1;
vis_right[row+col] = 1;
maximum = max(maximum, grid[row][col] + MaxNQueens(col+1, grid));
vis_row[row] = 0;
vis_left[col-row+N-1] = 0;
vis_right[row+col] = 0;
}
}
return maximum;
}
void solve() {
vector<vector<int>> grid(8, vector<int>(8));
for (int i=0; i<N; i++) for (int j=0; j<N; j++) cin >> grid[i][j];
cout << MaxNQueens(0, grid) << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
ll t=1; cin >> t;
while (t--) { solve(); }
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgbGwgbG9uZyBsb25nCiNkZWZpbmUgUEkgMy4xNDE1OTI2NTM1OQojZGVmaW5lIERQKHgsIHkpIG1lbXNldCh4LCB5LCBzaXplb2YgeCkKI2RlZmluZSBhbGwoeCkgeC5iZWdpbigpLCB4LmVuZCgpCiNkZWZpbmUgcmVhZCh4KSBmcmVvcGVuKCJ4IiwgInIiLCBzdGRpbik7CiNkZWZpbmUgd3JpdGUoeCkgZnJlb3BlbigieCIsICJ3Iiwgc3Rkb3V0KTsKCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgpsbCBnY2QobGwgYSxsbCBiKSB7IHdoaWxlKGIpIHsgbGwgeCA9IGE7IGEgPSBiOyBiID0geCAlIGI7IH0gcmV0dXJuIGE7IH0KbGwgbGNtKGxsIGEsbGwgYikgeyByZXR1cm4gYSAvIGdjZChhLCBiKSAqIGI7IH0KbGwgbkMyKGxsIG4pIHsgcmV0dXJuIChuKSoobi0xKS8yOyB9CmxsIHN1bW1pbmcobGwgbikgeyByZXR1cm4gKG4pKihuKzEpOyB9Cgpjb25zdCBpbnQgTiA9IDg7CmludCB2aXNfY29sWzUwXSA9IHswfTsKaW50IHZpc19yb3dbNTBdID0gezB9OwppbnQgdmlzX3JpZ2h0WzUwXSA9IHswfTsKaW50IHZpc19sZWZ0WzUwXSA9IHswfTsKCgppbnQgTWF4TlF1ZWVucyhpbnQgY29sLCB2ZWN0b3I8dmVjdG9yPGludD4+JmdyaWQpIHsKCiAgICBpZiAoY29sID09IE4pIHsKICAgICAgICByZXR1cm4gMDsKICAgIH0KCiAgICBpbnQgbWF4aW11bSA9IDA7CgogICAgZm9yIChpbnQgcm93PTA7IHJvdzxOOyByb3crKykgewoKICAgICAgICBpZiAoKHZpc19yb3dbcm93XSA9PSAwKSAmJiAodmlzX2xlZnRbY29sLXJvdytOLTFdID09IDApICYmICh2aXNfcmlnaHRbcm93K2NvbF0gPT0gMCkpIHsKCiAgICAgICAgICAgIHZpc19yb3dbcm93XSA9IDE7CiAgICAgICAgICAgIHZpc19sZWZ0W2NvbC1yb3crTi0xXSA9IDE7CiAgICAgICAgICAgIHZpc19yaWdodFtyb3crY29sXSA9IDE7CgogICAgICAgICAgICBtYXhpbXVtID0gbWF4KG1heGltdW0sIGdyaWRbcm93XVtjb2xdICsgTWF4TlF1ZWVucyhjb2wrMSwgZ3JpZCkpOwoKICAgICAgICAgICAgdmlzX3Jvd1tyb3ddID0gMDsKICAgICAgICAgICAgdmlzX2xlZnRbY29sLXJvdytOLTFdID0gMDsKICAgICAgICAgICAgdmlzX3JpZ2h0W3Jvdytjb2xdID0gMDsKCiAgICAgICAgfQogICAgfQoKICAgIHJldHVybiBtYXhpbXVtOwp9Cgp2b2lkIHNvbHZlKCkgewoKICAgIHZlY3Rvcjx2ZWN0b3I8aW50Pj4gZ3JpZCg4LCB2ZWN0b3I8aW50Pig4KSk7CgogICAgZm9yIChpbnQgaT0wOyBpPE47IGkrKykgZm9yIChpbnQgaj0wOyBqPE47IGorKykgY2luID4+IGdyaWRbaV1bal07CgogICAgY291dCA8PCBNYXhOUXVlZW5zKDAsIGdyaWQpIDw8ICJcbiI7Cgp9CgppbnQgbWFpbigpCnsKICAgIGlvczo6c3luY193aXRoX3N0ZGlvKGZhbHNlKTsKICAgIGNpbi50aWUobnVsbHB0ciksIGNvdXQudGllKG51bGxwdHIpOwoKICAgIGxsIHQ9MTsgY2luID4+IHQ7CiAgICB3aGlsZSAodC0tKSB7IHNvbHZlKCk7IH0KCiAgICByZXR1cm4gMDsKfQo=