The Painter's Problem

Problem Background

Special for beginners, ^_^

Problem Description

There is a square wall made of $N \times N$ square bricks, some white and some yellow.

Bob is a painter who wants to paint all the bricks yellow, but his brush is faulty. When he paints the brick at position $(i, j)$, the bricks at positions $(i-1, j)$, $(i+1, j)$, $(i, j-1)$, and $(i, j+1)$ also change color.

Please help Bob compute the minimum number of bricks he must paint so that all bricks become yellow.

Input Format

The first line is an integer $n\ (1 \le n \le 15)$, the size of the wall.

The next $n$ lines describe the initial state of the wall. Each line contains $n$ characters. The $j$-th character of the $i$-th line represents the color of the brick at position $(i, j)$. w means a white brick, y means a yellow brick.

Output Format

One line. If Bob can turn all bricks yellow, output the minimum number of bricks to paint; otherwise output inf.

Sample Input

5
wwwww
wwwww
wwwww
wwwww
wwwww

Sample Output

15

Constraints

1s, 1024KiB for each test case.