/* Problem 6--The Sultan's Successors
   The chess queen problem is a standard computer problem.  Here you
   essentially have to find ALL ways to place the queens so as to
   compute the best score. */

#include <stdio.h>
#include <stdlib.h>

FILE *in, *out;

int Board[8][8], max, ct, tot, BVal[8][8];

int main (int argc, char **argv);
void Process (void);
void Recurse (int pos);
int val (int r, int c);

int main (int argc, char **argv) {

  int ct, i;

 in = fopen ("prob6.in","r");
 out = fopen ("prob6.out","w");
 fscanf (in,"%d",&ct); /* get number of cases */
 for (i=0;i<ct;i++)
  Process (); /* process each case */
 fclose (in);
 fclose (out);
 return EXIT_SUCCESS;
}

/* Process reads in a board configuration and computes the best way to
   place the queens. */
void Process (void) {

  int i, j;

 for (i=0;i<8;i++)
  for (j=0;j<8;j++)  /* Read in the board */
   fscanf (in,"%d",&Board[i][j]);
 max= 0;
 Recurse (0); /* Get best way to place the queens */
 fprintf (out,"%d\n",max);
}

/* Recurse accepts the position number at which the next queen should be
   placed if possible, and recursively computes the best way to place
   the eight queens. */
void Recurse (int pos) {

  int i, k, r, c, bad;

 if (ct==8) { /* If all 8 queens are placed, is this the best way to */
  if (tot > max) max = tot; /* do it, so far? */
  return;
 }
 for (i=pos; i < 63; i++) { /* Go through and place queens on the rest*/
  r = i/8; c = i%8;   /* of the board */
  bad = 0;
  for (k=1; k < 8  && !bad; k++)  /* See whether square i is attacked */
   bad = val(r+k,c)||val(r-k,c)||val(r,c+k)||val(r,c-k)||val(r+k,c+k)
         ||val(r+k,c-k)||val(r-k,c+k)||val(r-k,c-k);
  if (!bad) { /* If it's not,k place the queen */
   BVal[r][c] = 1;
   tot += Board[r][c];
   ct++;
   Recurse (i+1); /* Try adding queens to the rest of the board */
   ct--;   /* Remove the queen to place it elsewhere */
   tot -= Board[r][c];
   BVal[r][c] = 0;
  }
 }
}

/* val returns whether a given square has a queen on it.  If the square
   doesn't exist then there is no queen there. */
int val (int r, int c) {
 if (r < 0 || r > 7 || c < 0 || c > 7) return 0;
 return BVal[r][c];
}