페그 퍼즐

페그 게임은 여러 가지 모양의 판에서 즐길 수 있지만, 목표는 언제나 같다. 판 위에 남는 페그(말)의 개수를 최대한 적게 만드는 것이다. 이를 위해 다음과 같은 이동을 반복한다. 하나의 페그가 바로 옆에 붙어 있는 다른 페그를 뛰어넘어, 그 반대편의 빈 칸에 착지한다. 뛰어넘어진 페그는 즉시 판에서 제거된다.

이동은 가로 또는 세로 방향으로만 할 수 있다. 즉, 페그 $A$의 바로 옆 칸에 페그 $B$가 있고 $B$의 한 칸 너머가 비어 있으면, $A$는 $B$를 뛰어넘어 그 빈 칸으로 이동하고 $B$는 제거된다.

페그 판의 초기 배치가 주어질 때, 최적의 이동 순서를 따랐을 때 판에 남게 되는 페그의 개수를 구하여라.

판은 다음 기호로 표현한다.

• . : 페그가 없는 빈 칸
• o : 페그가 놓인 칸
• # : 사용할 수 없는 칸 (페그를 놓을 수도, 지나갈 수도 없음)

아래는 표준적인 5×5 십자 모양 판의 예시다. 그림 A는 빈 판, 그림 B는 페그 5개가 놓인 판, 그림 C는 그림 B에서 최적의 이동을 마친 결과다. 그림 C에는 페그가 1개만 남아 있으며, 이는 어떤 게임에서도 얻을 수 있는 최선의 결과다. 이러한 최적의 이동 순서가 유일하지는 않을 수 있다.

그림 A (빈 판):

#...#
.....
.....
.....
#...#

그림 B (페그 5개):

#.o.#
..o..
oo.o.
.....
#...#

그림 C (최적 이동 후):

#...#
.....
...o.
.....
#...#

주어지는 판이 모두 같은 모양은 아니다. 모든 판은 5×5 크기이며, 페그가 적어도 1개, 빈 칸이 적어도 1개, 사용할 수 없는 칸이 적어도 4개 있다. 하지만 그 배치는 위 예시와 크게 다를 수 있다.

첫째 줄에 분석할 판의 개수 $n$이 주어진다.

이어지는 $5n$개의 줄에 판들이 주어진다. 각 판은 5개의 줄로 이루어지며, 각 줄은 위에서 설명한 기호(., o, #) 5개로 이루어진 문자열이다.

각 판에 대해, 최적의 이동을 모두 마친 뒤 판에 남는 페그의 개수를 $Y$라 할 때, 다음 문장을 한 줄에 출력한다.

The best case ends with Y pegs.

여기서 Y는 실제로 남은 페그의 개수로 바꾸어 출력한다.