Pegs

Peg games can be played on boards of many shapes, but the goal is always the same: to finish with as few pegs on the board as possible. You do this by making a sequence of moves. In one move, a peg jumps over an adjacent peg and lands in the empty space directly on the opposite side; the peg that was jumped over is immediately removed from the board.

Moves are made horizontally or vertically only. That is, if peg $A$ has a peg $B$ in the cell immediately next to it and the cell just beyond $B$ is empty, then $A$ jumps over $B$ into that empty cell and $B$ is removed.

Given the starting configuration of a peg board, determine the number of pegs that remain if the player makes the best possible sequence of moves.

A board is written with the following symbols:

• . : an empty hole (no peg)
• o : a peg
• # : a non-playable space (no peg may sit on it or pass through it)

Below is a standard 5×5 cross-shaped board. Figure A is an empty board, Figure B holds five pegs, and Figure C is the result of an optimal sequence of moves starting from Figure B. Figure C ends with a single peg, the best possible result for any game. Such an optimal sequence of moves need not be unique.

Figure A (empty board):

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

Figure B (five pegs):

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

Figure C (after an optimal sequence):

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

Not every board has the same shape. Every board is 5×5 and has at least one peg, at least one empty cell, and at least four non-playable spaces, but the layout may differ drastically from the example above.

The first line contains a single integer $n$, the number of boards to analyze.

The next $5n$ lines contain the boards, five lines per board. Each line is five characters drawn from the symbols above (., o, and #).

For each board, print one line giving the number of pegs left after an optimal set of jumps. Let $Y$ be that number and print:

The best case ends with Y pegs.

with Y replaced by the actual number of remaining pegs.