The Sultan's Successors

Interview

Time limit1sMemory limit128 MB

Summary

For each 8x8 board, place 8 non-attacking queens to maximize the sum of the numbers on the occupied squares.

Level: Medium4 of 10
Topics: Backtracking, Recursion, Brute force, Implementation
Solved: No attempts yet

Problem

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.)

Input

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$ .

Output

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

Examples4

Example 1

Input

1
 1  2  3  4  5  6  7  8
 9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
48 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

Expected output

Example 2

Input

1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Expected output

Example 3

Input

1
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99
99 99 99 99 99 99 99 99

Expected output

Example 4

Input

2
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1

Expected output

  260
    8