술탄의 후계자들

누비아의 술탄에게는 자식이 없어서, 자신이 죽으면 나라를 최대 $k$개의 지역으로 나누어 각 지역을 어떤 시험에서 가장 뛰어난 성적을 낸 사람에게 물려주기로 했다. 한 사람이 둘 이상의 지역을, 심지어 모든 지역을 물려받을 수도 있다.

지혜로운 사람만이 후계자가 되도록, 술탄은 다음과 같은 시험을 고안했다. 큰 홀 안에 $k$개의 체스판을 놓는다. 각 체스판은 $8 \times 8$ 격자이며, 모든 칸에는 $1$부터 $99$까지의 수가 하나씩 적혀 있고, $8$개의 퀸이 함께 주어진다. 각 지원자는 어떤 퀸도 다른 퀸을 위협하지 않도록 $8$개의 퀸을 판 위에 놓아야 하며, 선택된 칸에 적힌 수들의 합이 술탄이 미리 정한 값 이상이 되도록 해야 한다.

(체스 규칙에 따르면, 이는 각 행과 각 열에 정확히 하나의 퀸이 있고, 각 대각선에는 퀸이 최대 하나만 있어야 함을 의미한다.)

각 체스판에 대해, 서로 위협하지 않는 $8$개의 퀸을 놓아 얻을 수 있는 수들의 합의 최댓값을 구하는 프로그램을 작성하여라. (술탄은 뛰어난 체스 기사이자 훌륭한 수학자이므로, 그녀가 정한 점수는 얻을 수 있는 최댓값이다.)

첫째 줄에 체스판의 개수 $k$가 주어진다 ($1 \le k \le 20$). 이어서 $k$개의 체스판이 주어진다. 각 체스판은 $8$개의 줄에 각각 $8$개의 정수가 적힌 형태, 즉 총 $64$개의 수로 주어지며, 각 수는 $100$보다 작은 양의 정수이다.

각 체스판에 대해 얻을 수 있는 최대 점수를 한 줄에 하나씩 출력한다. 각 점수는 너비 $5$의 칸에 오른쪽 정렬하여 출력한다.