学步园

//纯八皇后问题，没什么好说的
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
int map[10][10];
int sum, max, C[20000];
void dfs( int cur )
{
	int i, j, ok;
	if( cur == 8 )
	{
		sum = 0;
		for( i = 0; i < 8; i++ )
			sum += map[i][C[i]];
		if( sum > max )
			max = sum;
	}
	else for( i = 0; i < 8; i++ )
	{
		ok = 1;
		C[cur] = i;
		for( j = 0; j < cur; j++ )
			if( C[cur] == C[j] || i-cur == C[j]-j || i+cur == C[j] + j )
			{	ok = 0;	break; }
		if( ok )
		{
			dfs( cur+1 );
		}
	}
}
int main()
{
	int N, i, j;
	scanf( "%d", &N );
	while( N-- )
	{
		for( i = 0; i < 8; i++ )
		{
			for( j = 0; j < 8; j++ )
				scanf( "%d", &map[i][j] );
			scanf( "\n" );
		}
		max = -1;
		dfs( 0 );
		printf( "%5d\n", max );
	}
	return 0;
}