Pegs

Time limit1sMemory limit128 MB

Summary

Given a 5x5 peg solitaire board with empty, peg, and blocked cells, find the minimum number of pegs reachable by any sequence of horizontal or vertical jumps.

Level: Medium7 of 10
Topics: DFS, Backtracking, Brute force, Bit manipulation
Solved: No attempts yet

Problem

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.

Input

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 #).

Output

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.

Examples1

Example 1

Input

3
#.o.#
..o..
oo.o.
.....
#...#
#...#
o.o.o
....o
...o.
#o..#
#..##
.o..#
ooo.o
.o.o.
#..o#

Expected output

The best case ends with 1 pegs.
The best case ends with 4 pegs.
The best case ends with 2 pegs.