#include <vector>
#include <set>
#include <iostream>

#include <stdlib.h>

using namespace std;

/*
 * DEBUG ONLY: If compiled -DDEBUG, the most favorable board layout for each
 * player will be printed to stderr. If compiled -DSTEP, every board position
 * searched will be printed.
 */

/* Maximum dimensions of the playing board */
#define MAXDIM 26

/* Maximum number of players */
#define MAXPLAYER 4

/* Return the maximum of two numbers */
#define max(a,b) ((a) > (b) ? (a) : (b))

/* A convenient way to represent a single coordinate */
typedef pair<int, int> point_t;

/* List of manipulators for all players in a dataset */
typedef vector<point_t> manip_t[MAXPLAYER];

/* Set of all manipulators; used to check for occupied cells */
typedef set<point_t> set_t;

/* Lookup table mapping player number to their ASCII character in the input */
const char avatar[MAXPLAYER] = {
    '!', '@', '#', '$'
};

/* Size of the hex grid used in the current dataset */
int size;

/* Number of players in the current dataset */
int players;

/*
 * Optimization: Precompute what the influence of each cell is for the initial
 * board configuration. Each element in init_influence[][] is 0, 1, 2, or 3 if
 * that player has influence over the cell or -1 if this cell is neutral. The
 * distance from each cell to the closest manipulator is also precomputed and
 * stored in init_distance[][]. Precomputing the distances allows us to later
 * recompute the influence of any given cell in O(1) time.
 */
int init_influence[MAXDIM][MAXDIM];
int init_distance[MAXDIM][MAXDIM];

/* Lookup the player number for a given ASCII avatar character */
int find_avatar(char id)
{
    int i;

    for(i = 0; i < MAXPLAYER; i++) {
        if(avatar[i] == id) {
            break;
        }
    }
    
    /* SANITY CHECK: Verify character used is valid for number of players */
    if(i >= players) {
        cerr << "Unknown character in grid: " << id << endl;
        throw;
    }
    
    return i;
}

/* Calculate the distance in cells between two points in a hex grid */
int length(point_t p1, point_t p2)
{
    point_t diff(p1.first - p2.first, p1.second - p2.second);

    /* If row and col directions have the same sign (or one is zero) */
    if(diff.first * diff.second >= 0) {
        return abs(diff.first) + abs(diff.second);
    }
    
    /* If the directions have different signs */
    else {
        return max(abs(diff.first), abs(diff.second));
    }
}

/*
 * Precompute the influence and distance to closest manipulator for the initial
 * board configuration. Tha "manip" argument is a list of all manipulators
 * in this data set.
 */
void precompute(manip_t &manip)
{
    /* Precompute each cell on the board */
    for(int row = 0; row < size; row++) {
        for(int col = 0; col < size; col++) {

            int mindist = 9999999;
            int minplayer = -1;
            point_t cell(row, col);    

            /* Check the distance to every manipluator of every player */
            for(int player = 0; player < players; player++) {
                for(int i = 0; i < manip[player].size(); i++) {

                    int dist = length(cell, manip[player][i]);

                    /*
                     * If the cell is equidistant to multiple manipulators
                     * owned by different players, then it may potentially be
                     * neutral if no shorter distance is found to any other
                     * manipulator.
                     */
                    if(dist == mindist && player != minplayer) {
                        minplayer = -1;
                    }

                    /*
                     * Otherwise, minimum distance decides the controlling
                     * player.
                     */
                    if(dist < mindist) {
                        mindist = dist;
                        minplayer = player;
                    }
                }
            }
            
            /* Cache the minimum distance and influence that was found */
            init_influence[row][col] = minplayer;
            init_distance[row][col] = mindist;
        }
    }
}

/*
 * Compute the new influence for a given "cell" on the hex grid assuming that
 * "current_player" has added a new manipulator at position "manip". Return the
 * player number that would control "cell" with the extra manipulator added or
 * return -1 if "cell" would be neutral. When influence() is called while
 * computing the initial board layout (i.e. before any extra manipulators are
 * added), a dummy value of (-1,-1) is used for "manip".
 *
 * DEBUG ONLY: If "print" is true, print out a representation of the board with
 * the new manipulator added:  Print a player's avatar character if this cell
 * contains a manipulator, print out a number if this cell is under the
 * player's influence, or print a dot if the cell is neutral.
 */
int influence(point_t cell, point_t manip, int current_player, bool print)
{  
    int cache_distance = init_distance[cell.first][cell.second];
    int cache_influence = init_influence[cell.first][cell.second];
    
    int new_distance = length(cell, manip);
    int influence_player;

    bool known = true;
    
    /* If computing the initial score, return only the precomputed influence */
    if(manip == point_t(-1,-1)) {
        influence_player = cache_influence;
    }

    /*
     * If the new manipulator at location "manip" is closer than any others
     * on the board, then it takes influence of "cell" and it will be under
     * the control of "current_player".
     */
    else if(new_distance < cache_distance) {
        influence_player = current_player;
    }
    
    /*
     * If an existing manipulator is closer to "cell" than the new
     * manipulator, then "manip" cannot possibly influence "cell" in any way
     * and the influence on "cell" remains the same.
     */
    else if(new_distance > cache_distance) {
        influence_player = cache_influence;        
    }
    
    /*
     * If the new manipulator at location "manip" is the same distance as
     * at least one other existing manipulator, then three possibilities
     * exist based on the previous influence on "cell":
     *
     * 1. If "cell" was under the influence of another player, then adding
     * our own manipulator at the same distance will force the cell to become
     * neutral.
     *
     */
    else if(current_player != cache_influence && cache_influence != -1) {
        influence_player = -1;
    }
    
    /*
     * 2. If "cell" was previously neutral, then it had at least two
     * manipulators that are owned by different players and at the same
     * distance away. If a third manipulator is added, the cell will continue
     * to remain neutral.
     *
     * 3. If "cell" was previously under the influence of "current_player"
     * then all of the closest manipulators (if there is more than one) must
     * also be owned by "current_player". Adding an additional manipulator
     * owned by the same player will not change the cell's influence.
     */
    else {
        influence_player = cache_influence;        
    }

    /* DEBUG ONLY */
    if(print) {
        if(new_distance == 0 || cache_distance == 0) {
            cerr << avatar[influence_player] << " ";
        }
        else if(influence_player == -1) {
            cerr << ". ";
        }
        else {
            cerr << influence_player + 1 << " ";
        }
    }
    
    return influence_player;
}

/*
 * Compute and return the total score for the specified "player" if an
 * additional manipulator was added at location "manip". The score is computed
 * by iterating over every cell in the grid and counting how many are under the
 * influence of the given player's manipulators.
 *
 * DEBUG ONLY: If "print" is true, print the hex grid back out using digits to
 * indicate the influence that each cell is under.
 */
int score(int player, point_t manip, bool print)
{
    int score = 0;

    for(int row = 0; row < size; row++) {

        /* DEBUG ONLY: Print leading spaces to make rhombus shape */
        if(print) {
            for(int i = 0; i < row; i++) {
                cerr << " ";
            }
        }

        for(int col = 0; col < size; col++) {

            /* Only count cells with influence belonging to this player */
            if(influence(point_t(row, col), manip, player, print) == player) {
                score++;
            }
        }

        /* DEBUG ONLY */
        if(print) {
            cerr << endl;
        }
    }

    /* DEBUG ONLY */
    if(print) {
        cerr << "Player " << player + 1 << " score: " << score << endl << endl;
    }
    
    return score;
}

/*
 * Find and return the maximum attainable score for a given "player" by
 * trying to add one extra manipulator for that player at every remaining
 * free position on the board (i.e. any position not in the "occupied" set).
 * If the board is full, simply return the player's score for the initial
 * board configuration.
 *
 * DEBUG ONLY: Print the board leyout for every search step (-DSTEP) or print
 * the board layout for the most valuable board (-DDEBUG)
 */
int search(int player, manip_t &manip, set_t &occupied)
{
    /* Compute initial score with no additional manipulators added */
#ifdef STEP
    int maxscore = score(player, point_t(-1, -1), true);
#else
    int maxscore = score(player, point_t(-1, -1), false);
#endif

#ifdef DEBUG
    /*
     * DEBUG ONLY: Remember the most favorable position found so far for
     * adding a new manipulator. If no additional manipulators could be added
     * to increase the player's score (for example, the board is completely
     * full) then "maxcell" remains set to (-1,-1).
     */
    point_t maxcell(-1,-1);
#endif

    /* Try every possible board position */
    for(int row = 0; row < size; row++) {
        for(int col = 0; col < size; col++) {
            point_t cell(row, col);

            /* Skip cells already occupied by another manipulator */
            if(occupied.find(cell) != occupied.end()) {
                continue;
            }

            /* Calculate maximum possible score for this configuration */
#ifdef STEP
            int curscore = score(player, cell, true);
#else
            int curscore = score(player, cell, false);
#endif
            if(curscore > maxscore) {
                maxscore = curscore;
#ifdef DEBUG
                maxcell = cell;
#endif
            }
        }
    }
        
#ifdef DEBUG
    /* DEBUG ONLY: Print most favorable board configuration */
    score(player, maxcell, true);        
#endif

    return maxscore;
}

/* Main body of program */
void process(void)
{
    int data_num, data_idx;
    
    /* Read how many data sets to process */
    cin >> data_num;
    
    /* Process each data set separately */
    for(data_idx = 0; data_idx < data_num; data_idx++) {
            
        /* Read in the number of players and board size for this data set */
        cin >> players >> size;
        
        /* SANITY CHECK: Verify board size and number of players */
        if(players < 2 || players > MAXPLAYER || size < 1 || size > MAXDIM) {
            cerr << "Invalid board size or number of players" << endl;
            throw;
        }

        /* Lists/set of manipulators for all possible players */
        manip_t manip;
        set_t occupied;
        
        /* Read in the initial board layout */
        for(int row = 0; row < size; row++) {
            for(int col = 0; col < size; col++) {
                char c;                
                cin >> c;
                
                /* Skip over blank grid space and only record manipulators */
                if(c != '.') {
                    int player = find_avatar(c);                    
                    point_t pos = point_t(row, col);

                    manip[player].push_back(pos);
                    occupied.insert(pos);
                }
            }
        }
        
        /* Print output heading */
        cout << "DATA SET #" << data_idx + 1 << endl;
#if defined(DEBUG) || defined(STEP)
        cerr << "DATA SET #" << data_idx + 1 << endl << endl;
#endif
        
        /* Compute the initial influences and manipulator distances */
        precompute(manip);
        
        /* Print maximum attainable score by each player's last move */
        for(int i = 0; i < players; i++) {        
            cout << search(i, manip, occupied) << endl;
        }
    }
}

/* Run program and print out any exceptions that occur */
int main(void)
{
    /* Throw exceptions on failed data extraction in >> operator */
    cin.exceptions(ios::failbit);
    
    /* Run main body of code */
    try {
        process();
    }
    
    /* Catch unexpected EOF or bad input data */
    catch(ios::failure const &e) {
        cerr << "Unexpected EOF or data type mismatch on input" << endl;
    }

    return 0;
}