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;
bool a[52][52];
int f[52][52][52][52];
int x[52][52];
int y[52][52];
int X[52][52];
int Y[52][52];
int mx[52][52][52][2];
int Mx[52][52][52][2];
int n, i, j, I, J, k, l, L, R, mxx, mxy, Mxx, Mxy;
char ch;
int main() {
  scanf("%d\n", &n);
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      scanf("%c", &ch);
      if (ch == '#') a[i][j] = 1;
    }
    scanf("\n");
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      mx[i][j][j - 1][0] = 2133333333;
      mx[i][j][j - 1][1] = 2133333333;
      Mx[i][j][j - 1][0] = -2133333333;
      Mx[i][j][j - 1][1] = -2133333333;
      for (k = j; k <= n; k++) {
        mx[i][j][k][0] = mx[i][j][k - 1][0];
        mx[i][j][k][1] = mx[i][j][k - 1][1];
        Mx[i][j][k][0] = Mx[i][j][k - 1][0];
        Mx[i][j][k][1] = Mx[i][j][k - 1][1];
        if (a[i][k]) {
          mx[i][j][k][0] = (mx[i][j][k][0] < k ? mx[i][j][k][0] : k);
          Mx[i][j][k][0] = (Mx[i][j][k][0] > k ? Mx[i][j][k][0] : k);
        }
        if (a[k][i]) {
          mx[i][j][k][1] = (mx[i][j][k][1] < k ? mx[i][j][k][1] : k);
          Mx[i][j][k][1] = (Mx[i][j][k][1] > k ? Mx[i][j][k][1] : k);
        }
      }
    }
  }
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      memset(x, 1, sizeof(x));
      memset(y, 1, sizeof(y));
      memset(X, 128, sizeof(X));
      memset(Y, 128, sizeof(Y));
      for (k = i; k <= n; k++) {
        for (l = j; l <= n; l++) {
          x[k][l] = (x[k - 1][l] < x[k][l - 1] ? x[k - 1][l] : x[k][l - 1]);
          y[k][l] = (y[k - 1][l] < y[k][l - 1] ? y[k - 1][l] : y[k][l - 1]);
          X[k][l] = (X[k - 1][l] > X[k][l - 1] ? X[k - 1][l] : X[k][l - 1]);
          Y[k][l] = (Y[k - 1][l] > Y[k][l - 1] ? Y[k - 1][l] : Y[k][l - 1]);
          if (a[k][l]) {
            x[k][l] = (x[k][l] < k ? x[k][l] : k);
            y[k][l] = (y[k][l] < l ? y[k][l] : l);
            X[k][l] = (X[k][l] > k ? X[k][l] : k);
            Y[k][l] = (Y[k][l] > l ? Y[k][l] : l);
          }
          if (x[k][l] > n)
            f[i][j][k][l] = 0;
          else
            f[i][j][k][l] = (X[k][l] - x[k][l] + 1 > Y[k][l] - y[k][l] + 1
                                 ? X[k][l] - x[k][l] + 1
                                 : Y[k][l] - y[k][l] + 1);
        }
      }
    }
  }
  for (L = 1; L <= n; L++) {
    for (R = 1; R <= n; R++) {
      for (i = 1; i <= n - L + 1; i++) {
        I = i + L - 1;
        for (j = 1; j <= n - R + 1; j++) {
          J = j + R - 1;
          mxx = 2133333333;
          mxy = 2133333333;
          Mxx = -2133333333;
          Mxy = -2133333333;
          for (k = i - 1; k >= 1; k--) {
            if (mx[k][j][J][0] <= n) {
              mxx = (mxx < k ? mxx : k);
              Mxx = (Mxx > k ? Mxx : k);
              mxy = (mxy < mx[k][j][J][0] ? mxy : mx[k][j][J][0]);
              Mxy = (Mxy > Mx[k][j][J][0] ? Mxy : Mx[k][j][J][0]);
            }
            if (mxx > n)
              f[k][j][I][J] = (f[k][j][I][J] < f[i][j][I][J] ? f[k][j][I][J]
                                                             : f[i][j][I][J]);
            else
              f[k][j][I][J] =
                  (f[k][j][I][J] <
                           f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                                ? Mxx - mxx + 1
                                                : Mxy - mxy + 1)
                       ? f[k][j][I][J]
                       : f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                              ? Mxx - mxx + 1
                                              : Mxy - mxy + 1));
          }
          mxx = 2133333333;
          mxy = 2133333333;
          Mxx = -2133333333;
          Mxy = -2133333333;
          for (k = I + 1; k <= n; k++) {
            if (mx[k][j][J][0] <= n) {
              mxx = (mxx < k ? mxx : k);
              Mxx = (Mxx > k ? Mxx : k);
              mxy = (mxy < mx[k][j][J][0] ? mxy : mx[k][j][J][0]);
              Mxy = (Mxy > Mx[k][j][J][0] ? Mxy : Mx[k][j][J][0]);
            }
            if (mxx > n)
              f[i][j][k][J] = (f[i][j][k][J] < f[i][j][I][J] ? f[i][j][k][J]
                                                             : f[i][j][I][J]);
            else
              f[i][j][k][J] =
                  (f[i][j][k][J] <
                           f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                                ? Mxx - mxx + 1
                                                : Mxy - mxy + 1)
                       ? f[i][j][k][J]
                       : f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                              ? Mxx - mxx + 1
                                              : Mxy - mxy + 1));
          }
          mxx = 2133333333;
          mxy = 2133333333;
          Mxx = -2133333333;
          Mxy = -2133333333;
          for (k = j - 1; k >= 1; k--) {
            if (mx[k][i][I][1] <= n) {
              mxy = (mxy < k ? mxy : k);
              Mxy = (Mxy > k ? Mxy : k);
              mxx = (mxx < mx[k][i][I][1] ? mxx : mx[k][i][I][1]);
              Mxx = (Mxx > Mx[k][i][I][1] ? Mxx : Mx[k][i][I][1]);
            }
            if (mxx > n)
              f[i][k][I][J] = (f[i][k][I][J] < f[i][j][I][J] ? f[i][k][I][J]
                                                             : f[i][j][I][J]);
            else
              f[i][k][I][J] =
                  (f[i][k][I][J] <
                           f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                                ? Mxx - mxx + 1
                                                : Mxy - mxy + 1)
                       ? f[i][k][I][J]
                       : f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                              ? Mxx - mxx + 1
                                              : Mxy - mxy + 1));
          }
          mxx = 2133333333;
          mxy = 2133333333;
          Mxx = -2133333333;
          Mxy = -2133333333;
          for (k = J + 1; k <= n; k++) {
            if (mx[k][i][I][1] <= n) {
              mxy = (mxy < k ? mxy : k);
              Mxy = (Mxy > k ? Mxy : k);
              mxx = (mxx < mx[k][i][I][1] ? mxx : mx[k][i][I][1]);
              Mxx = (Mxx > Mx[k][i][I][1] ? Mxx : Mx[k][i][I][1]);
            }
            if (mxx > n)
              f[i][j][I][k] = (f[i][j][I][k] < f[i][j][I][J] ? f[i][j][I][k]
                                                             : f[i][j][I][J]);
            else
              f[i][j][I][k] =
                  (f[i][j][I][k] <
                           f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                                ? Mxx - mxx + 1
                                                : Mxy - mxy + 1)
                       ? f[i][j][I][k]
                       : f[i][j][I][J] + (Mxx - mxx + 1 > Mxy - mxy + 1
                                              ? Mxx - mxx + 1
                                              : Mxy - mxy + 1));
          }
        }
      }
    }
  }
  printf("%d\n", f[1][1][n][n]);
}
