经典八皇后问题变形，求出存在权值的情况下的最大值；
// File Name: 1033.cpp
// Author: bo_jwolf
// Created Time: 2014年02月03日 星期一 18时37分57秒
#include<vector>
#include<list>
#include<map>
#include<set>
#include<deque>
#include<stack>
#include<bitset>
#include<algorithm>
#include<functional>
#include<numeric>
#include<utility>
#include<sstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
const int maxn = 105;
int num[ maxn ][ maxn ], vis[ maxn ][ maxn ],Max;
void Dfs(int cur,int sum){
if( cur == 8 ){
Max = Max > sum ? Max : sum;
return;
}
for(int i = 0; i < 8; ++i ){
if( !vis[ 0 ][ i ] && !vis[ 1 ][ 8 + cur - i ] && !vis[ 2 ][ cur + i ] ){
vis[ 0 ][ i ] = vis[ 1 ][ 8 + cur - i ] = vis[ 2 ][ cur + i ] = 1;
Dfs( cur + 1, sum + num[ cur ][ i ] );
vis[ 0 ][ i ] = vis[ 1 ][ 8 + cur - i ] = vis[ 2 ][ cur + i ] = 0;
}
}
}
int main(){
int n;
cin >> n;
while( n-- ){
for( int i = 0; i < 8; i++ ){
for( int j = 0; j < 8; j++ ){
cin >> num[ i ][ j ];
}
}
Max = 0;
memset( vis, 0, sizeof( vis ) );
Dfs( 0, 0 );
cout << setw( 5 ) << Max << endl;
}
return 0;
}