또 다른 형태의 진실

Influence는 보드 게임이다. 거의 모든 형태의 판에서 즐길 수 있지만, 흥미로운 형태 중 하나는 마름모처럼 생긴 육각형 $N \times N$ 격자다.

9×9 판의 예시는 다음과 같다.

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

행에는 위에서 아래로 A부터 I까지, 열에는 1부터 9까지 이름이 붙는다. 이 격자에서 칸 F5는 F4, F6, E5, E6, G4, G5와 인접한다. (이 좌표 이름은 인접 관계를 설명하기 위한 것일 뿐이며 입력에는 등장하지 않는다.)

Influence의 관련 규칙은 다음과 같다.

• 플레이어는 번갈아 가며 조종자(Manipulator)를 놓는다. 조종자는 한 칸을 차지하며, 한 칸에는 최대 한 개의 조종자만 놓을 수 있다. 빈 칸이 없으면 해당 플레이어는 차례를 넘겨야 한다.
• 각 플레이어는 영향력(Influence)을 가진다. 어떤 칸이 다른 모든 플레이어의 조종자보다 그 플레이어의 조종자 중 하나에 엄격히 더 가까우면, 그 칸은 해당 플레이어에게 영향력 1점을 준다. 여기서 거리는 직선 거리가 아니라, 판 위에서 인접한 칸을 따라가는 최단 경로의 이동 칸 수다. 예를 들어 F5는 G6까지 2칸, G5까지 1칸, 자기 자신까지 0칸이다. 둘 이상의 플레이어로부터 같은 거리에 있는(동점인) 칸은 누구에게도 영향력을 주지 않는다. 조종자가 하나도 없는 플레이어의 영향력은 0이다.

게임이 끝났을 때 영향력이 가장 큰 플레이어가 이긴다. 예를 들어 세 명이 플레이할 때 어떤 배치에서는 첫 번째 플레이어(!)가 영향력 2점, 두 번째 플레이어(@)가 10점, 세 번째 플레이어(#)가 4점을 얻고, 9개의 칸은 동점이어서 누구에게도 가지 않는다.

각 플레이어에 대해, 그 플레이어가 마지막 수 한 번을 최적으로 두었을 때 가질 수 있는 최대 영향력을 구하라. 즉, 가장 좋은 빈 칸 하나에 조종자를 추가로 놓거나, 판이 가득 찼다면 차례를 넘긴 경우다. 각 플레이어의 최선의 수는 원래 판을 기준으로 독립적으로 계산하며, 다른 플레이어가 수를 둔 뒤의 판을 사용하지 않는다.

첫 줄에는 데이터 집합의 개수 $N$ ($1 \le N \le 100$)이 주어진다. 각 데이터 집합은 다음으로 이루어진다.

• 플레이어 수 $P$ ($2 \le P \le 4$)가 적힌 한 줄;
• 판의 크기 $D$ ($1 \le D \le 26$)가 적힌 한 줄 ($D = 9$는 위의 9×9 판이다);
• 위에서 아래로 판을 나타내는 $D$개의 줄. 각 줄에서 칸은 공백으로 구분되며, 각 칸은 다음 중 하나다.
  • . — 빈 칸;
  • ! — 첫 번째 플레이어의 조종자;
  • @ — 두 번째 플레이어의 조종자;
  • # — 세 번째 플레이어의 조종자 ($P \ge 3$일 때만);
  • $ — 네 번째 플레이어의 조종자 ($P \ge 4$일 때만).

판을 나타내는 줄에는 위의 기울어진 배치를 흉내 내기 위한 여분의 앞쪽 공백이 있을 수 있으며, 이 여분의 공백은 의미가 없다.

각 데이터 집합에 대해 DATA SET #K 줄을 출력한다. 여기서 $K$는 첫 번째 데이터 집합이면 1, 두 번째면 2, 이런 식이다. 그다음 $P$개의 줄을 출력하는데, 순서대로 첫 번째, 두 번째, 세 번째(플레이할 때), 네 번째(플레이할 때) 플레이어가 원래 판에서 마지막 수 한 번으로 얻을 수 있는 최대 영향력을 출력한다.