Peg Solitaire

Peg solitaire is played on a two dimensional board with holes in it. Each hole takes one peg.

A peg moves only by jumping over a peg that is horizontally or vertically adjacent to it and landing in the hole right behind that peg. The landing hole must be empty, and the peg that was jumped over comes off the board.

You are given the pegs on the board. Move the pegs so that as few pegs as possible are left, and find the smallest number of moves that leaves that many pegs.

The first line contains the number of test cases $N$. ($1 \le N \le 100$)

Each test case is the starting board, five lines of nine characters each. Every board has the same shape. The first and the fifth line have holes only in positions 4 to 6, and the second through the fourth line have holes in all nine positions.

. is an empty hole, o is a hole with a peg in it, and # is a position with no hole. A board holds at most 8 pegs. A blank line separates consecutive test cases.

For each test case, print two integers on one line, separated by a space. The first is the smallest number of pegs that can be left on the board, and the second is the smallest number of moves needed to reach that number.