Problem Description

You are given a $7 \times 7$ matrix representing a peg solitaire board.

On the board, the first two rows and the last two rows have their first two columns as blank spaces (if this is hard to understand, see the sample). In the remaining cells, o means there is a peg, and . means the cell is empty.

For any peg, if there is an adjacent peg directly above, below, left, or right of it, and the cell on the other side in that direction is empty, then it can jump over the adjacent peg. The jumped-over peg is removed from the board. This is counted as one move.

Find the maximum number of moves that can be made on this board.

Input Format

Input a board.

Output Format

Output the maximum number of moves.

  ooo  
  ooo  
ooooooo
ooo.ooo
ooooooo
  ooo  
  ooo  

4

  ooo  
  ooo  
..ooo..
oo...oo
..ooo..
  ooo  
  ooo   

12

Hint

Notes

This problem is translated from COCI2007-2008 CONTEST #1 T2 PEG

Translated by ChatGPT 5