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
/*  -*- coding: utf-8 -*-
 *
 * 3016.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 127;
const int INF = 1 << 29;

/* typedef */

typedef vector<int> vi;

/* global variables */

int xss[MAX_N + 1][MAX_N + 1];

/* subroutines */

inline int xsum(int x0, int y0, int x1, int y1) {
  return (xss[y1][x1] - xss[y1][x0] - xss[y0][x1] + xss[y0][x0]);
}

inline bool hline(int y, int x0, int x1) {
  return (xsum(x0, y, x1, y + 1) == x1 - x0);
}

inline bool vline(int x, int y0, int y1) {
  return (xsum(x, y0, x + 1, y1) == y1 - y0);
}

int rec(int x0, int y0, int x1, int y1) {
  vi vx, vy;
  for (int y = y0 + 1; y < y1; y += 2)
    if (hline(y, x0, x1)) vy.push_back(y);
  for (int x = x0 + 1; x < x1; x += 2)
    if (vline(x, y0, y1)) vx.push_back(x);
  
  int minsum = INF;

  for (vi::iterator yit = vy.begin(); yit != vy.end(); yit++)
    for (vi::iterator xit = vx.begin(); xit != vx.end(); xit++) {
      int yy = *yit, xx = *xit;
      int sum = 1;
      if (xsum(x0, y0, xx, yy) > 0) {
	int r = rec(x0, y0, xx, yy);
	if (r >= INF) continue;
	sum += r;
      }
      if (xsum(xx + 1, y0, x1, yy) > 0) {
	int r = rec(xx + 1, y0, x1, yy);
	if (r >= INF) continue;
	sum += r;
      }
      if (xsum(x0, yy + 1, xx, y1) > 0) {
	int r = rec(x0, yy + 1, xx, y1);
	if (r >= INF) continue;
	sum += r;
      }
      if (xsum(xx + 1, yy + 1, x1, y1) > 0) {
	int r = rec(xx + 1, yy + 1, x1, y1);
	if (r >= INF) continue;
	sum += r;
      }

      if (minsum > sum) minsum = sum;
    }

  return minsum;
}

/* main */

int main() {
  int n;
  scanf("%d", &n);

  for (int y = 0; y < n; y++) {
    char s[MAX_N + 4];
    scanf("%s", s);
    for (int x = 0; x < n; x++)
      xss[y + 1][x + 1] =
	((s[x] == 'x') ? 1 : 0) + xss[y + 1][x] + xss[y][x + 1] - xss[y][x];
  }

  if (xsum(0, 0, n, n) == 0) {
    puts("0");
    return 0;
  }

  printf("%d\n", rec(0, 0, n, n));
  return 0;
}

