Each chessboard has integer scores in the range from 0 to 100 written on each grid, and it is provided with 8 pieces of queens.
The task is to place the 8 queens on the chessboard such that no queen takes another one and the sum of scores on the grids occupied by the queens is maximized .
(Rule: each row, column, and diagonal can only have one queen.)
The first line of the input is an integer T indicating the number of test cases.
The following lines contain T sets of numbers for the T test cases.
Each set has 64 numbers indicating the scores of the chessboard, amd each number will be a non-negative integer no larger than 100.
Each test case is separated by a blank line. T <= 20.
The output contains T lines.
Each line shows the maximum sum of scores for the corresponding test case.
There is a '\n' at the end of each line.