Another Version of the Truth

Influence is a board game. It can be played on almost any layout, but an interesting one is a hexagonal $N \times N$ grid shaped like a rhombus.

An example 9×9 board looks like this:

1 2 3 4 5 6 7 8 9
 \ \ \ \ \ \ \ \ \
  * * * * * * * * * — A
   * * * * * * * * * — B
    * * * * * * * * * — C
     * * * * * * * * * — D
      * * * * * * * * * — E
       * * * * * * * * * — F
        * * * * * * * * * — G
         * * * * * * * * * — H
          * * * * * * * * * — I

Rows are labeled A through I from top to bottom, and columns are labeled 1 through 9. On this grid, cell F5 is adjacent to F4, F6, E5, E6, G4, and G5. (These coordinate labels only explain the adjacencies; they never appear in the input.)

The relevant rules of Influence are:

• Players take turns placing Manipulators. A Manipulator occupies one location, and each location holds at most one Manipulator. If no empty location remains, the player must pass.
• Each player has an amount of Influence: one point for every location that is strictly closer to one of that player's Manipulators than to any other player's Manipulator. Distance is not straight-line distance; it is the number of steps in a shortest path of adjacent cells that stays on the board. For example, F5 is 2 steps from G6, 1 step from G5, and 0 steps from itself. A location that is tied between two or more players (equally distant) counts for no one. A player with no Manipulators has 0 Influence.

The player with the most Influence at the end of the game wins. For instance, with three players one arrangement gives the first player (!) 2 Influence, the second player (@) 10 Influence, and the third player (#) 4 Influence, while 9 tied locations count for no one.

For each player, report the maximum Influence that player could hold after a single optimal last move: placing one additional Manipulator on the best empty location, or passing if the board is full. Every player's best move is evaluated independently on the original board, never on a board already changed by another player's move.

The first line contains an integer $N$ ($1 \le N \le 100$), the number of data sets. Each data set consists of:

• a line with an integer $P$ ($2 \le P \le 4$), the number of players;
• a line with an integer $D$ ($1 \le D \le 26$), the board dimension ($D = 9$ gives the 9×9 board shown above);
• $D$ lines describing the board from top to bottom. On each line the cells are separated by spaces, and every cell is one of:
  • . — an empty location;
  • ! — a Manipulator of the first player;
  • @ — a Manipulator of the second player;
  • # — a Manipulator of the third player (only when $P \ge 3$);
  • $ — a Manipulator of the fourth player (only when $P \ge 4$).

The board lines may contain extra leading spaces so the input resembles the slanted layout above; this extra whitespace is not significant.

For each data set, print a line DATA SET #K, where $K$ is 1 for the first data set, 2 for the second, and so on. Then print $P$ lines: the maximum Influence achievable by the first, second, third (when playing), and fourth (when playing) player, in that order, each from a single optimal last move computed on the original board.