1. 

/*

* ACM Programming Contest

* Problem: 167 - The Sultan's Successors

* Status: Accepted

* Language: C

* Runtime: 0.000

* Date: 2009-05-04 19:30:20

* Author: Axel Fiedler

*/
#include <stdio.h>
#include <string.h>

#define SIZE 8
#define SOLUTIONS 92
#define MAX_BOARDS 20

int board[SIZE][SIZE];
int maxSum[MAX_BOARDS];

int solutions[SOLUTIONS][SIZE] = { {0, 4, 7, 5, 2, 6, 1, 3}, {0, 5, 7, 2, 6, 3, 1, 4},
{0, 6, 3, 5, 7, 1, 4, 2}, {0, 6, 4, 7, 1, 3, 5, 2},
{1, 3, 5, 7, 2, 0, 6, 4}, {1, 4, 6, 0, 2, 7, 5, 3},
{1, 4, 6, 3, 0, 7, 5, 2}, {1, 5, 0, 6, 3, 7, 2, 4},
{1, 5, 7, 2, 0, 3, 6, 4}, {1, 6, 2, 5, 7, 4, 0, 3},
{1, 6, 4, 7, 0, 3, 5, 2}, {1, 7, 5, 0, 2, 4, 6, 3},
{2, 0, 6, 4, 7, 1, 3, 5}, {2, 4, 1, 7, 0, 6, 3, 5},
{2, 4, 1, 7, 5, 3, 6, 0}, {2, 4, 6, 0, 3, 1, 7, 5},
{2, 4, 7, 3, 0, 6, 1, 5}, {2, 5, 1, 4, 7, 0, 6, 3},
{2, 5, 1, 6, 0, 3, 7, 4}, {2, 5, 1, 6, 4, 0, 7, 3},
{2, 5, 3, 0, 7, 4, 6, 1}, {2, 5, 3, 1, 7, 4, 6, 0},
{2, 5, 7, 0, 3, 6, 4, 1}, {2, 5, 7, 0, 4, 6, 1, 3},
{2, 5, 7, 1, 3, 0, 6, 4}, {2, 6, 1, 7, 4, 0, 3, 5},
{2, 6, 1, 7, 5, 3, 0, 4}, {2, 7, 3, 6, 0, 5, 1, 4},
{3, 0, 4, 7, 1, 6, 2, 5}, {3, 0, 4, 7, 5, 2, 6, 1},
{3, 1, 4, 7, 5, 0, 2, 6}, {3, 1, 6, 2, 5, 7, 0, 4},
{3, 1, 6, 2, 5, 7, 4, 0}, {3, 1, 6, 4, 0, 7, 5, 2},
{3, 1, 7, 4, 6, 0, 2, 5}, {3, 1, 7, 5, 0, 2, 4, 6},
{3, 5, 0, 4, 1, 7, 2, 6}, {3, 5, 7, 1, 6, 0, 2, 4},
{3, 5, 7, 2, 0, 6, 4, 1}, {3, 6, 0, 7, 4, 1, 5, 2},
{3, 6, 2, 7, 1, 4, 0, 5}, {3, 6, 4, 1, 5, 0, 2, 7},
{3, 6, 4, 2, 0, 5, 7, 1}, {3, 7, 0, 2, 5, 1, 6, 4},
{3, 7, 0, 4, 6, 1, 5, 2}, {3, 7, 4, 2, 0, 6, 1, 5},
{4, 0, 3, 5, 7, 1, 6, 2}, {4, 0, 7, 3, 1, 6, 2, 5},
{4, 0, 7, 5, 2, 6, 1, 3}, {4, 1, 3, 5, 7, 2, 0, 6},
{4, 1, 3, 6, 2, 7, 5, 0}, {4, 1, 5, 0, 6, 3, 7, 2},
{4, 1, 7, 0, 3, 6, 2, 5}, {4, 2, 0, 5, 7, 1, 3, 6},
{4, 2, 0, 6, 1, 7, 5, 3}, {4, 2, 7, 3, 6, 0, 5, 1},
{4, 6, 0, 2, 7, 5, 3, 1}, {4, 6, 0, 3, 1, 7, 5, 2},
{4, 6, 1, 3, 7, 0, 2, 5}, {4, 6, 1, 5, 2, 0, 3, 7},
{4, 6, 1, 5, 2, 0, 7, 3}, {4, 6, 3, 0, 2, 7, 5, 1},
{4, 7, 3, 0, 2, 5, 1, 6}, {4, 7, 3, 0, 6, 1, 5, 2},
{5, 0, 4, 1, 7, 2, 6, 3}, {5, 1, 6, 0, 2, 4, 7, 3},
{5, 1, 6, 0, 3, 7, 4, 2}, {5, 2, 0, 6, 4, 7, 1, 3},
{5, 2, 0, 7, 3, 1, 6, 4}, {5, 2, 0, 7, 4, 1, 3, 6},
{5, 2, 4, 6, 0, 3, 1, 7}, {5, 2, 4, 7, 0, 3, 1, 6},
{5, 2, 6, 1, 3, 7, 0, 4}, {5, 2, 6, 1, 7, 4, 0, 3},
{5, 2, 6, 3, 0, 7, 1, 4}, {5, 3, 0, 4, 7, 1, 6, 2},
{5, 3, 1, 7, 4, 6, 0, 2}, {5, 3, 6, 0, 2, 4, 1, 7},
{5, 3, 6, 0, 7, 1, 4, 2}, {5, 7, 1, 3, 0, 6, 4, 2},
{6, 0, 2, 7, 5, 3, 1, 4}, {6, 1, 3, 0, 7, 4, 2, 5},
{6, 1, 5, 2, 0, 3, 7, 4}, {6, 2, 0, 5, 7, 4, 1, 3},
{6, 2, 7, 1, 4, 0, 5, 3}, {6, 3, 1, 4, 7, 0, 2, 5},
{6, 3, 1, 7, 5, 0, 2, 4}, {6, 4, 2, 0, 5, 7, 1, 3},
{7, 1, 3, 0, 6, 4, 2, 5}, {7, 1, 4, 2, 0, 6, 3, 5},
{7, 2, 0, 5, 1, 4, 6, 3}, {7, 3, 0, 2, 5, 1, 6, 4}};

int main()
{
int n, maxValue, sum, k, i, j;

scanf("%d", &n);

for (k = 0; k < n; k++)
{
for (i = 0; i < SIZE; i++)
for (j = 0; j < SIZE; j++)
scanf("%d", &board[i][j]);

maxValue = 0;

for (i = 0; i < SOLUTIONS; i++)
{
sum = 0;

for (j = 0; j < SIZE; j++)
sum += board[j][solutions[i][j]];

if (sum > maxValue)
maxValue = sum;
}

maxSum[k] = maxValue;
}

for (i = 0; i < n; i++)
printf("%5d\n", maxSum[i]);

return 0;

}