There is a square grid of size n × n. Some cells are colored in black, all others are colored in white. In one operation you can select some rectangle and color all its cells in white. It costs max(h, w) to color a rectangle of size h × w. You are to make all cells white for minimum total cost.

Input

The first line contains a single integer n (1 ≤ n ≤ 50) — the size of the square grid.

Each of the next n lines contains a string of length n, consisting of characters '.' and '#'. The j-th character of the i-th line is '#' if the cell with coordinates (i, j) is black, otherwise it is white.

Output

Print a single integer — the minimum total cost to paint all cells in white.

Examples

Input


3
###
#.#
###


Output


3


Input


3
...
...
...


Output


0


Input


4
#...
....
....
#...


Output


2


Input


5
#...#
.#.#.
.....
.#...
#....


Output


5

Note

The examples and some of optimal solutions are shown on the pictures below.

<image>
#include <bits/stdc++.h>
using namespace std;
template <typename T, typename T1>
T amax(T &a, T1 b) {
  if (b > a) a = b;
  return a;
}
template <typename T, typename T1>
T amin(T &a, T1 b) {
  if (b < a) a = b;
  return a;
}
long long int n;
long long int dp[51][51][51][51];
char arr[51][51];
bool isPrime(long long int n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long int i = 5; i * i <= n; i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0) return false;
  return true;
}
long long int pw(long long int x, long long int y) {
  long long int i = 0;
  long long int ans = 1;
  for (i = 1; i <= y; ++i) ans = (ans * x) % 998244353;
  return ans;
}
long long int fact(long long int n) {
  long long int ans = 1;
  for (long long int i = 1; i <= n; ++i) ans = (ans * i) % 1000000007;
  return ans;
}
long long int helper(long long int i1, long long int j1, long long int i2,
                     long long int j2) {
  if (dp[i1][j1][i2][j2] != -1) return dp[i1][j1][i2][j2];
  long long int ans = max(abs(i1 - i2), abs(j1 - j2)) + 1ll;
  for (long long int i = i1; i <= i2 - 1; ++i)
    ans = min(ans, helper(i1, j1, i, j2) + helper(i + 1, j1, i2, j2));
  for (long long int i = j1; i <= j2 - 1; ++i)
    ans = min(ans, helper(i1, j1, i2, i) + helper(i1, i + 1, i2, j2));
  return dp[i1][j1][i2][j2] = ans;
}
void solve() {
  unordered_map<long long int, long long int> um1, um2;
  map<long long int, long long int> m2;
  string s, s1, s2, s3, s4, t;
  char ch1, ch2, ch3;
  long long int m{}, k{}, i{}, j{}, x{}, y{}, z{}, u{}, l{}, h{}, w{}, o{}, p{},
      q{}, r{}, a{}, b{}, c{}, d{}, e{}, sum{}, ans{}, ans2{10000000},
      ans1{10000000};
  cin >> n;
  memset(dp, -1, sizeof(dp));
  long long int wc, bc;
  for (i = 0; i < n; ++i) {
    for (j = 0; j < n; ++j) {
      cin >> arr[i][j];
      if (arr[i][j] == '#')
        dp[i][j][i][j] = 1;
      else
        dp[i][j][i][j] = 0;
    }
  }
  ans = helper(0, 0, n - 1, n - 1);
  cout << ans << ("\n");
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  solve();
}
