Problem Description

You are playing a target shooting game on a $4 \times 4$ grid.

In the grid, the target at the $i$-th row from the top and the $j$-th column from the left is represented by $S_{i,j}$. If $S_{i,j}$ is ., there is no target, and if $S_{i,j}$ is #, there is a target. The game is cleared when all targets are hit at least once.

When you aim at a square and throw a ball, it will fly to the aimed square or one square away in any of the four directions (including outside the grid) with a probability of $\frac{1}{5}$. If there is a target at the destination, it is considered a hit.

By appropriately choosing the squares to aim at as the game progresses, what is the minimum expected number of throws required to clear the game?

Input Format

The input is given from the standard input in the following format:

$ S_{1,1}S_{1,2}S_{1,3}S_{1,4} $ $ S_{2,1}S_{2,2}S_{2,3}S_{2,4} $ $ S_{3,1}S_{3,2}S_{3,3}S_{3,4} $ $ S_{4,1}S_{4,2}S_{4,3}S_{4,4} $

Output Format

Output the minimum expected number of throws.

The answer will be considered correct if the absolute or relative error is within $10^{-6}$.

Sample Input and Output

Sample Input #1

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

Sample Output #1

5.0000000000

Sample Input #2

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

Sample Output #2

7.5000000000

Sample Input #3

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

Sample Output #3

10.4166666667

Sample Input #4

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

Sample Output #4

32.5674089515

Notes/Hints

Constraints

• $S_{i,j}$ is either . or #
• At least one of $S_{i,j}$ is #

Sample Explanation 1

The expected number of throws until the ball hits the target is $5$. The ball may fly outside the grid.

Sample Explanation 2

Aim at the upper target until the ball hits one of the two targets. After hitting one, aim at the remaining target.

Sample Explanation 3

Initially, aiming at the empty square in the center of the four targets is optimal.

见题面 Input 部分

见题面 Output 部分