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 <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <vector>
#include <set>
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct Sum2D {
	vector<vector<ll>> b;
	Sum2D() {};
	Sum2D(const vector<vector<ll>>& a) {
		int H = a.size(), W = a[0].size();
		b = a;
		for(int i = 0; i < H; i++)
		for(int j = 0; j < W - 1; j++) b[i][j + 1] += b[i][j];
		for(int j = 0; j < W; j++)
		for(int i = 0; i < H - 1; i++) b[i + 1][j] += b[i][j];
	}
	// ?????????
	ll sum(int x1, int y1, int x2, int y2) {
		ll ret = b[y2][x2];
		if(y1 - 1 >= 0) ret -= b[y1 - 1][x2];
		if(x1 - 1 >= 0) ret -= b[y2][x1 - 1];
		if(y1 - 1 >= 0 && x1 - 1 >= 0) ret += b[y1 - 1][x1 - 1];
		return ret;
	}
};
Sum2D S;

//D
int N;

bool in(int x, int y) {
	return 0 <= x && x < N && 0 <= y && y < N;
}

string A[128];
int dp[64][64][64][64];
int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };

vector<int> cross[128];

int conv(int x1, int y1, int x2, int y2) {
	int ret = x1;
	ret = ret * 128 + y1;
	ret = ret * 128 + x2;
	ret = ret * 128 + y2;
	return ret;
}

map<int, int> dpm;

int f(int x1, int y1, int x2, int y2) {
	if(x2 < x1 || y2 < y1) return 0;
	int hash = conv(x1, y1, x2, y2);
	if(dpm.count(hash)) return dpm[hash];
	//if(dp[x1][y1][x2][y2] >= 0) return dp[x1][y1][x2][y2];
	//int& d = dp[x1][y1][x2][y2];
	int H = y2 - y1 + 1, W = x2 - x1 + 1;
	if(S.sum(x1, y1, x2, y2) == 0) return 0;
	int d = 1000;
	for(int y = y1; y <= y2; y++) {
		for(auto x : cross[y]) {
			if(x1 <= x && x <= x2) {
				if(S.sum(x1, y, x2, y) != W) continue;
				if(S.sum(x, y1, x, y2) != H) continue;
				int sum = 1;
				sum += f(x1, y1, x - 1, y - 1);
				sum += f(x + 1, y1, x2, y - 1);
				sum += f(x1, y + 1, x - 1, y2);
				sum += f(x + 1, y + 1, x2, y2);
				d = min(d, sum);
			}
		}
	}
	return dpm[hash] = d;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	cin >> N;
	vector<vector<ll>> b(N);
	for(int i = 0; i < N; i++) {
		cin >> A[i];
		for(int j = 0; j < N; j++) {
			b[i].push_back(A[i][j] == 'x');
		}
	}
	S = Sum2D(b);
	for(int y = 0; y < N; y++) {
		for(int x = 0; x < N; x++) {
			if(A[y][x] == 'o') continue;
			bool ok = true;
			for(int k = 0; k < 4; k++) {
				int nx = x + dx[k], ny = y + dy[k];
				if(in(nx, ny) && A[ny][nx] == 'o') {
					ok = false;
					break;
				}
			}
			if(ok) cross[y].push_back(x);
		}
	}
	memset(dp, -1, sizeof dp);
	cout << f(0, 0, (N - 1), (N - 1)) << endl;
}