Background

Special for beginners, ^_^

Description

有一个正方形的墙，由 $N\times N$ 个正方形的砖组成，其中一些砖是白色的，另外一些砖是黄色的。

Bob 是个画家，想把全部的砖都涂成黄色，但他的画笔不好使。当他用画笔涂画第 $(i, j)$ 个位置的砖时， 位置 $(i-1, j)、 (i+1, j)、 (i, j-1)、 (i, j+1)$ 上的砖都会改变颜色。

请你帮助 Bob 计算出最少需要涂画多少块砖，才能使所有砖的颜色都变成黄色。

Format

Input

第一行是一个整数 $n (1\le n\le 15)$，表示墙的大小。

接下来的 $n$ 行表示墙的初始状态。每一行包含 $n$ 个字符。

第 $i$ 行的第 $j$ 个字符表示位于位置 $(i,j)$ 上的砖的颜色。$w$ 表示白砖，$y$ 表示黄砖。

Output

一行，如果 Bob 能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出 inf。

Samples

5
wwwww
wwwww
wwwww
wwwww
wwwww

15

Limitation

1s, 1024KiB for each test case.