#!/usr/bin/env python

# A solution for Influence, written in Python.
# by Phil Bordelon

# 0 1 2
#  . . . 0 
#   . . . 1
#    . . . 2
#
# (1,1) is adjacent to (1,0), (1,2), (0,1), (2,1) (the obvious ones),
# plus (2,0) and (0,2) (the less-obvious ones).

import os
import sys

# This number should be larger than any possible distance in the problem.
MAX_DISTANCE = 999

# This number should be the maximum size of the grid.
MAX_SIZE = 26

# Debug?
DEBUG = os.getenv("DEBUG", False)

def distance (x1, y1, x2, y2):

   # Calculate the raw numeric differences.  We also need the magnitudes
   # of the differences, for the "less-obvious" adjacency math.
   x_delta = x2 - x1
   y_delta = y2 - y1
   x_delta_mag = abs(x_delta)
   y_delta_mag = abs(y_delta)

   # First, do the math if it's the less-obvious adjacencies, which only
   # occurs if the two deltas are going in different directions.
   if (x_delta < 0 and y_delta > 0) or (x_delta > 0 and y_delta < 0):

      # The distance is the number of steps diagonally (taken from
      # both numbers), plus the length of the larger leg.  So the
      # math can be done as short leg + (long leg - short leg).
      if x_delta_mag < y_delta_mag:
         distance = x_delta_mag + (y_delta_mag - x_delta_mag)
      else:
         distance = y_delta_mag + (x_delta_mag - y_delta_mag)
   else:

      # Boring distance math.
      distance = x_delta_mag + y_delta_mag

   return distance

def precalcGrid ():

   # We precalculate the distances for every cell from every other cell,
   # because this makes the actual solution phase of the problem a series
   # of calls into look-up tables.

   grid = {}
   for x1 in range(MAX_SIZE):
      for y1 in range(MAX_SIZE):
         new_location = {}
         for x2 in range(MAX_SIZE):
            for y2 in range(MAX_SIZE):
               new_location[(x2,y2)] = distance(x1, y1, x2, y2)
         grid[(x1,y1)] = new_location

   return grid

def drawBoard(grid, size):

   # This is a quick little debug function that draws a representation of the
   # board.
   lookup = (".", "!", "@", "#", "$")
   for i in range(size):
      for x in range(i):
         print " ",
      for j in range(size):
         if grid[(i,j)]["piece"] > 0:
            print " %s " % lookup[grid[(i,j)]["piece"]],
         else:
            print "%s%02d" % (lookup[grid[(i,j)]["closest_owner"]], grid[(i,j)]["closest_distance"]),
      print

def calculateScoreAndUpdateGrid(grid):
   
   # As the rather verbose function title states, this function calculates the
   # score for various players given a particular board layout, along with
   # updating the grid's knowledge of the closest pieces to each location,
   # which is used for when we try to place new pieces.  Yes, it's bad form to
   # do both of these things in the same function, but it makes sense to not
   # run through the board twice, and this /is/ programming contest code.

   # Easy part first; start scores out as the count of pieces.
   for i in range(4):
      grid[i + 1]["score"] = grid[i + 1]["count"]

   # Loop through the empty spaces on the grid.
   for i, j in grid["emptylist"]:
      
      # For each location, find the owner, if any, and the distance to
      # said closest piece.  This is easy.  We loop over every pieces on the
      # board and find the closest ones.  If there's more than one player
      # with the closest pieces, no one owns it.
      closest_owner = 0
      closest_distance = MAX_DISTANCE
      for k, l, owner in grid["piecelist"]:
         distance = grid[(i,j)][(k,l)]
         if distance < closest_distance:

            # Clear new winner.  Record.
            closest_distance = distance
            closest_owner = owner
         elif distance == closest_distance:

            # If two players are closest, we need to set the owner to
            # zero.  If we've already determined it's contested, it
            # needs to stay that way.
            if closest_owner > 0 and owner != closest_owner:

               # The piece is contested.
               closest_owner = 0

      # Save the closest distance and closest owner.
      grid[(i,j)]["closest_distance"] = closest_distance
      grid[(i,j)]["closest_owner"] = closest_owner

      # If the closest owner is an actual player (as opposed to the contested
      # value), increment their score.
      if closest_owner:
         grid[closest_owner]["score"] += 1

   # Return the updated grid.
   return grid
   
def setupGrid(grid, size):

   # Here we set up the grid for a particular data set, clearing out scores
   # and reading in the pieces and empty spaces from the input.

   # First, clear out the piece counts for each player.
   grid[1] = {"count": 0, "score": 0}
   grid[2] = {"count": 0, "score": 0}
   grid[3] = {"count": 0, "score": 0}
   grid[4] = {"count": 0, "score": 0}

   # Also clear out the lists of pieces and empty locations.
   grid["piecelist"] = []
   grid["emptylist"] = []

   # Now, read in each piece and put it in the grid, incrementing counts
   # as necessary.
   for i in range(size):
      line = sys.stdin.readline().strip()

      # Get the actual characters from the line, whitespace-free.
      pieces_in_line = [x for x in line.split() if len(x) > 0]

      # Mild error checking.
      if len(pieces_in_line) != size:
         sys.exit("ERROR: Wrong number of pieces in line with piece setup %s!" % line)

      # Loop through each piece in this line.
      for j in range(len(pieces_in_line)):
         piece = pieces_in_line[j]
         if piece == ".":

            # An empty space.  Append this location to the empty list, and set
            # its owner to no one.
            grid[(i,j)]["piece"] = 0
            grid["emptylist"].append((i,j))
         elif piece == "!":

            # A piece for the first player.  Add this location to the piece
            # list, increment their count of pieces by one, and set its owner
            # to the first player.
            grid[(i,j)]["piece"] = 1
            grid[1]["count"] += 1
            grid["piecelist"].append((i,j, 1))
         elif piece == "@":

            # The second player ...
            grid[(i,j)]["piece"] = 2
            grid[2]["count"] += 1
            grid["piecelist"].append((i,j, 2))
         elif piece == "#":

            # ... the third ...
            grid[(i,j)]["piece"] = 3
            grid[3]["count"] += 1
            grid["piecelist"].append((i,j, 3))
         elif piece == "$":

            # ... and the fourth.
            grid[(i,j)]["piece"] = 4
            grid[4]["count"] += 1
            grid["piecelist"].append((i,j, 4))

   # Now that we've read every piece in the grid, calculate each empty
   # space's shortest distance to a piece and the current score.
   grid = calculateScoreAndUpdateGrid(grid)

   # Return.
   return grid

def bestScore(grid, size, player):

   # Here we determine the best possible score for a player if they have
   # one more move.

   # The score can never be worse than the score the player already has.
   score = grid[player]["score"]
   best_additional_points = 0
   if DEBUG:
      best_spot = "NONE"

   # Now, try putting a piece for this player in each empty location.
   for i, j in grid["emptylist"]:

      additional_points = 0
      # Check every /other/ empty location to see if this spot is closer
      # to it than any other player's piece.
      for k, l in grid["emptylist"]:

         distance = grid[(i,j)][(k,l)]
         if distance < grid[(k,l)]["closest_distance"]:

            # Well, this is indeed closer than any other piece, but we
            # can't count the location twice if the player already /had/
            # the closest piece to this location.
            if player != grid[(k,l)]["closest_owner"]:
               additional_points += 1

      # Record this if it's the best number of additional points we've
      # found.
      if additional_points > best_additional_points:
         best_additional_points = additional_points

         if DEBUG:
            best_spot = (i,j)
 
   if DEBUG:
      print "The best spot is: " + repr(best_spot)

   # Return the best number of points we've found for this player.
   return score + best_additional_points

if "__main__" == __name__:

   # Precalculate the adjacencies for the grid.
   grid = precalcGrid()
   dataset_count = int(sys.stdin.readline())
   for dataset_loop in range(dataset_count):

      print "DATA SET #%d" % (dataset_loop + 1)

      # Get the count of players and the size of the board.
      player_count = int(sys.stdin.readline())
      size = int(sys.stdin.readline())

      # Read the board in, populating our representation with distances
      # to the nearest pieces.
      grid = setupGrid(grid, size)

      if DEBUG:
         drawBoard(grid, size)

      # Lastly, find the best new spots for pieces for each player.
      for i in range(player_count):
         print bestScore(grid, size, i + 1)