JMU F17 Week 10

Start

2017-11-06 23:00 CET

JMU F17 Week 10

End

2017-11-13 23:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -320 days 1:00:54

168:00:00

0:00:00

Problem DPebble Solitaire

I bet you have seen a pebble solitaire game. You know the game where you are given a board with an arrangment of small cavities, initially all but one occupied by a pebble each. The aim of the game is to remove as many pebbles as possible from the board. Pebbles disappear from the board as a result of a move. A move is possible if there is a straight line of three adjacent cavities, let us call them $A$, $B$, and $C$, with $B$ in the middle, where $A$ is vacant, but $B$ and $C$ each contain a pebble. The move consists of moving the pebble from $C$ to $A$, and removing the pebble in $B$ from the board. You may continue to make moves until no more moves are possible.

In this problem, we look at a simple variant of this game, namely a board with twelve cavities located along a line. In the beginning of each game, some of the cavities are occupied by pebbles. Your mission is to find a sequence of moves such that as few pebbles as possible are left on the board.

Input

The input begins with a positive integer $n \le 10$ on a line of its own. Thereafter $n$ different games follow. Each game consists of one line of input with exactly twelve characters, describing the twelve cavities of the board in order. Each character is either ‘-’ or ‘o’. A ‘-’ character denotes an empty cavity, whereas an ‘o’ character denotes a cavity with a pebble in it. There is at least one pebble in all games.

Output

For each of the $n$ games in the input, output the minimum number of pebbles left on the board possible to obtain as a result of moves, on a line of its own.

Sample Input 1 Sample Output 1
5
---oo-------
-o--o-oo----
-o----ooo---
oooooooooooo
oooooooooo-o

1
2
3
12
1