The Sultan's Successors

The Sultan of Nubia has no children, so she has decided that on her death the country will be split into up to $k$ separate parts, each inherited by whoever performs best on a test. One person may inherit more than one part, or even all of them.

To ensure that only highly intelligent people become her successors, the Sultan devised a test. In a large hall she places $k$ chessboards. Each chessboard is an $8 \times 8$ grid with a number from $1$ to $99$ written on every square, and comes with $8$ jewelled chess queens. Each candidate must place the $8$ queens on a board so that no queen attacks another, and so that the numbers on the chosen squares sum to a value at least as high as one chosen in advance by the Sultan.

(In chess this means that every row and every column contains exactly one queen, and every diagonal contains at most one queen.)

Write a program that reads the chessboards and, for each board, determines the highest possible sum obtainable by placing the $8$ non-attacking queens. (The Sultan is both a strong chess player and a fine mathematician, so the score she chose is the best attainable.)

The first line contains $k$, the number of boards ($1 \le k \le 20$). It is followed by $k$ boards. Each board is given as $8$ lines of $8$ integers, i.e. $64$ numbers in total, where every number is a positive integer less than $100$.

For each board, output one line containing its highest possible score. Each score is right-justified in a field $5$ characters wide.