Problem

There is a grid of $ N \ times N $ cells. Initially all cells are white. Follow the steps below to increase the number of black squares.

Select one white cell from the cells that are even-numbered from the top and even-numbered from the left. The selected square turns black. Further, the adjacent white squares also change to black in a chain reaction in each of the vertical and horizontal directions of the squares. This chain continues until there are no white cells in that direction. (An example is shown below)

□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
□□□□□□□□□
↓ Select the 4th from the top and the 6th from the left
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
■■■■■■■■■
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
↓ Select the second from the top and the second from the left
□ ■ □□□ ■ □□□
■■■■■■ □□□
□ ■ □□□ ■ □□□
■■■■■■■■■
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
□□□□□ ■ □□□
↓ Select 6th from the top and 8th from the left
□ ■ □□□ ■ □□□
■■■■■■ □□□
□ ■ □□□ ■ □□□
■■■■■■■■■
□□□□□ ■ □ ■ □
□□□□□ ■■■■
□□□□□ ■ □ ■ □
□□□□□ ■ □ ■ □
□□□□□ ■ □ ■ □


You want to create a grid where the color of the $ i $ th cell from the top and the $ j $ th cell from the left is $ A_ {i, j} $. Find the minimum number of times to select a square.

Constraints

The input satisfies the following conditions.

* $ 3 \ le N \ le 127 $
* $ N $ is odd
* $ A_ {i, j} $ is'o'or'x'
* Only input that can be made is given

Input

The input is given in the following format.

$ N $
$ A_ {1,1} $ $ A_ {1,2} $ ... $ A_ {1, N} $
$ A_ {2,1} $ $ A_ {2,2} $ ... $ A_ {2, N} $
...
$ A_ {N, 1} $ $ A_ {N, 2} $ ... $ A_ {N, N} $


When $ A_ {i, j} $ is'o', it means that the $ i $ th cell from the top and the $ j $ th cell from the left are white, and when it is'x', it is a black cell. Represents that.

Output

Outputs the minimum number of times to select a cell on the first line.

Examples

Input

5
oxooo
oxooo
oxooo
xxxxx
oxooo


Output

1


Input

9
oxoooooxo
oxxxxxxxx
oxoooooxo
xxxxxxxxx
oxoxooooo
oxxxxxxxx
oxoxoxooo
oxoxxxxxx
oxoxoxooo


Output

4
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define pb push_back

const int N = 64;
const int INF = 19191919;

int n;
string a[128];

int dx[4]={1,-1,0,0}, dy[4]={0,0,1,-1};
int dp[N][N][N][N];

bool is_candidate(int lx, int ly, int rx, int ry, int X, int Y)
{
    if(a[Y][X]!='x') return false;
    bool ret = true;
    for(int i=lx; i<=rx; ++i) ret &= (a[Y][i]=='x');
    for(int i=ly; i<=ry; ++i) ret &= (a[i][X]=='x');
    return ret;
}

int f(int lx, int ly, int rx, int ry)
{
    if(dp[lx/2][ly/2][rx/2][ry/2]<INF) return dp[lx/2][ly/2][rx/2][ry/2];

    // printf("CALL %d %d %d %d\n", lx,ly,rx,ry);

    bool is_empty=true;
    for(int i=ly; i<=ry; ++i)for(int j=lx; j<=rx; ++j)if(a[i][j]=='x') is_empty = false;
    if(is_empty) return 0;

    int ret = INF;
    for(int i=ly+1; i<ry; i+=2)for(int j=lx+1; j<rx; j+=2)
    {
        // ???????????????????£?
        if(is_candidate(lx,ly,rx,ry,j,i))
        {
            // printf("  !CANDIDATE %d %d\n", i,j);
            ret = min(ret, 1+f(lx,ly,j-1,i-1)+f(j+1,ly,rx,i-1)+f(lx,i+1,j-1,ry)+f(j+1,i+1,rx,ry));
        }
    }

    return dp[lx/2][ly/2][rx/2][ry/2] = ret;
}

int main()
{
    rep(i,N)rep(j,N)rep(k,N)rep(l,N) dp[i][j][k][l]=INF;

    cin >>n;
    rep(i,n) cin >>a[i];
    cout << f(0,0,n-1,n-1) << endl;
    return 0;
}