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>
using V = vector<T>;
template <typename T>
using VV = vector<V<T>>;
template <typename T>
using Mi = map<long long, T>;
template <typename T>
using MMi = map<long long, Mi<T>>;
const double PI = 3.141592653589793238463;
template <typename T>
istream &operator>>(istream &cin, V<T> &arr) {
  for (T &val : arr) {
    cin >> val;
  }
  return cin;
}
template <typename T>
ostream &operator<<(ostream &cout, VV<T> &arr) {
  for (V<T> &val : arr) {
    cout << val << '\n';
  }
  return cout;
}
template <typename T>
ostream &operator<<(ostream &cout, V<T> &arr) {
  for (T &val : arr) {
    cout << val << " ";
  }
  return cout;
}
template <typename T, typename R>
istream &operator>>(istream &cin, pair<T, R> &p) {
  cin >> p.first >> p.second;
  return cin;
}
template <typename T, typename R>
ostream &operator<<(ostream &cout, pair<T, R> &p) {
  cout << p.first << " " << p.second;
  return cout;
}
template <typename T>
V<T> &operator--(V<T> &arr) {
  for (T &val : arr) {
    val--;
  }
  return arr;
}
template <typename T>
V<T> &operator++(V<T> &arr) {
  for (T &val : arr) {
    val++;
  }
  return arr;
}
pair<long long, long long> zero = {-1, -1};
int xx[4] = {1, -1, 0, 0};
int yy[4] = {0, 0, 1, -1};
class Siev {
 public:
  V<int> prim;
  V<int> prims;
  long long n;
  Siev(long long n = 1e6) : n(n) {
    prim.resize(n + 1);
    for (int i = 0; i <= n; i++) {
      prim[i] = i;
    }
    for (long long i = 2; i <= n; i++) {
      if (prim[i] == i) {
        prims.push_back(i);
        for (long long j = i * i; j <= n; j += i) {
          if (prim[j] == j) {
            prim[j] = i;
          }
        }
      }
    }
  }
};
long long gcd(long long a, long long b) {
  if (a < b) {
    swap(a, b);
  }
  if (b == 0) {
    return a;
  }
  return gcd(b, a % b);
}
long long gcd(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1;
  long long d = gcd(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
long long lcm(long long a, long long b) {
  long long nod = gcd(a, b);
  long long ans = a / nod * b;
  return ans;
}
long long divup(long long a, long long b) {
  if (a % b == 0) {
    return a / b;
  } else {
    return a / b + 1;
  }
}
class SNM {
 private:
  vector<long long> parent;
  vector<long long> size;

 public:
  SNM(int n) {
    parent = vector<long long>(n);
    size = vector<long long>(n, 1);
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }
  void make_set(int v) { parent[v] = v; }
  int find_set(int v) {
    if (v == parent[v]) return v;
    long long ans = find_set(parent[v]);
    parent[v] = ans;
    return ans;
  }
  void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
      parent[b] = a;
      size[a] += size[b];
    }
  }
  long long getSize(int v) {
    v = find_set(v);
    return size[v];
  }
};
class LCA {
 private:
  long long N;
  long long n;
  vector<vector<long long>> up;
  vector<vector<long long>> g;
  vector<long long> lvl;
  void dfs(long long v, long long h) {
    lvl[v] = h;
    for (long long u : g[v]) {
      dfs(u, h + 1);
    }
  }

 public:
  LCA(vector<long long> &parent) {
    n = parent.size();
    N = log2(n) + 1;
    g = vector<vector<long long>>(n);
    lvl = vector<long long>(n);
    long long core = -1;
    for (int i = 0; i < n; i++) {
      if (parent[i] != -1) {
        g[parent[i]].push_back(i);
      } else {
        core = i;
      }
    }
    dfs(core, 0);
    up = vector<vector<long long>>(N, vector<long long>(n));
    up[0] = parent;
    for (int i = 1; i < N; i++) {
      for (int j = 0; j < n; j++) {
        long long parent = up[i - 1][j];
        if (parent == -1) {
          up[i][j] = -1;
        } else {
          up[i][j] = up[i - 1][parent];
        }
      }
    }
  }
  long long getParent(long long v, long long needUp) {
    for (int i = N - 1; i >= 0; i--) {
      if (up[i][v] != -1 && lvl[v] - lvl[up[i][v]] <= needUp) {
        needUp -= lvl[v] - lvl[up[i][v]];
        v = up[i][v];
      }
    }
    if (needUp != 0) {
      return -1;
    } else {
      return v;
    }
  }
  long long getLCA(long long a, long long b) {
    if (lvl[a] > lvl[b]) {
      long long del = abs(lvl[a] - lvl[b]);
      a = getParent(a, del);
    }
    if (lvl[a] < lvl[b]) {
      long long del = abs(lvl[a] - lvl[b]);
      b = getParent(b, del);
    }
    if (a == b) {
      return a;
    }
    for (int i = N - 1; i >= 0; i--) {
      if (up[i][a] != up[i][b]) {
        a = up[i][a];
        b = up[i][b];
      }
    }
    return up[0][a];
  }
  long long getLvl(long long v) { return lvl[v]; }
};
class Node {
 private:
  long long val;
  long long l;
  long long r;
  Node *lChildren;
  Node *rChildren;
  long long merge(Node *a, Node *b) { return max(a->val, b->val); }
  Node(long long l, long long r, vector<long long> &arr) {
    this->l = l;
    this->r = r;
    if (l == r) {
      val = arr[l];
    } else {
      long long mid = (l + r) / 2;
      lChildren = new Node(l, mid, arr);
      rChildren = new Node(mid + 1, r, arr);
      val = merge(lChildren, rChildren);
    }
  }

 public:
  Node(vector<long long> arr) : Node(0, arr.size() - 1, arr) {}
  long long getValue(long long left, long long right) {
    if (l == left && r == right) {
      return val;
    }
    long long mid = (l + r) / 2;
    long long ans = -1e18;
    if (left <= mid) {
      long long lp = lChildren->getValue(left, min(right, mid));
      ans = max(ans, lp);
    }
    if (right > mid) {
      long long rp = rChildren->getValue(max(mid + 1, left), right);
      ans = max(ans, rp);
    }
    return ans;
  }
  void update(long long l, long long r, long long value) {
    if (l == this->l && r == this->r) {
      val = value;
      return;
    }
    long long mid = (this->l + this->r) / 2;
    if (l <= mid) {
      lChildren->update(l, min(mid, r), value);
    }
    if (r > mid) {
      rChildren->update(max(mid + 1, l), r, value);
    }
    val = merge(lChildren, rChildren);
  }
};
void delR(long long v, vector<vector<long long>> &g, vector<bool> &viz,
          vector<vector<long long>> &G) {
  viz[v] = true;
  for (long long u : g[v]) {
    if (!viz[u]) {
      G[v].push_back(u);
      delR(u, g, viz, G);
    }
  }
}
class Drob {
 public:
  long long a = 0;
  long long b = 1;
  Drob(long long a, long long b = 1) : a(a), b(b) {
    long long nod = gcd(a, b);
    a /= nod;
    b /= nod;
  }
  Drob operator+(Drob &add) {
    long long na = a * add.b + add.a * b;
    long long nb = b * add.b;
    return Drob(na, nb);
  }
  Drob operator+=(Drob &add) { return *this + add; }
  Drob operator-(Drob &minus) { minus.a *= -1; }
  Drob operator-=(Drob &minus) { return *this - minus; }
  Drob operator*(Drob &d) {
    long long na = a * d.a;
    long long nb = b * d.b;
    return Drob(na, nb);
  }
  Drob operator*=(Drob &d) { return (*this) * d; }
  Drob operator/(Drob &d) {
    Drob dd(d.b, d.a);
    return (*this) * dd;
  }
  Drob operator/=(Drob &d) { return (*this) / d; }
  bool operator==(Drob &d) { return a == d.a && b == d.b; }
  bool operator>(Drob &d) {
    long long aa = a * d.b;
    long long ad = d.a * b;
    return aa > ad;
  }
};
void split(string &str, char &space, V<string> &ans) {
  auto i = str.begin();
  while (i != str.end()) {
    i = std::find_if(i, str.end(), [space](char c) { return c != space; });
    auto j = std::find_if(i, str.end(), [space](char c) { return c == space; });
    if (i != str.end()) {
      ans.push_back(std::string(i, j));
      i = j;
    }
  }
}
long long sumNumber(long long n) {
  long long sum = 0;
  while (n != 0) {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}
class Prefix {
  vector<long long> prefix;
  long long n;

 public:
  Prefix(vector<long long> &arr) {
    n = arr.size() + 1;
    prefix.resize(n);
    prefix[0] = 0;
    for (int i = 0; i < n - 1; i++) {
      prefix[i + 1] = prefix[i] + arr[i];
    }
  }
  long long sum(long long l, long long r) { return prefix[r + 1] - prefix[l]; }
};
class DPrefix {
  vector<vector<long long>> prefix;
  long long n;
  long long m;

 public:
  DPrefix(vector<vector<long long>> &matr) {
    long long n = matr.size() + 1;
    long long m = matr[0].size() + 1;
    prefix = vector<vector<long long>>(n, vector<long long>(m, 0));
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < m - 1; j++) {
        prefix[i + 1][j + 1] =
            prefix[i + 1][j] + prefix[i][j + 1] - prefix[i][j] + matr[i][j];
      }
    }
  }
  long long sum(pair<long long, long long> p1, pair<long long, long long> p2) {
    p2.first++;
    p2.second++;
    long long res = prefix[p1.first][p1.second] + prefix[p2.first][p2.second] -
                    prefix[p1.first][p2.second] - prefix[p2.first][p1.second];
  }
};
template <typename T>
class AV : public V<T> {
 public:
  AV() : V<T>(){};
  AV(long long n) : V<T>(n){};
  AV(long long n, long long val) : V<T>(n, val){};
  T sum() {
    T ans = 0;
    for (T &val : *this) {
      ans += val;
    }
    return ans;
  }
  T max() {
    T ans = (*this)[0];
    for (T &val : *this) {
      ans = std::max(ans, val);
    }
    return ans;
  }
  T min() {
    T ans = (*this)[0];
    for (T &val : *this) {
      ans = std::min(ans, val);
    }
    return ans;
  }
  void rsort() { std::sort(this->rbegin(), this->rend()); }
  void sort() { std::sort(this->begin(), this->end()); }
  long long bs(T &x) {
    V<T> &arr = *this;
    long long l = 0;
    long long r = arr.size();
    while (l < r) {
      long long mid = (l + r) / 2;
      if (arr[mid] > x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};
class MinQueue {
  deque<long long> q;

 public:
  long long getMin() { return q.front(); }
  void add(long long val) {
    while (!q.empty() && q.back() > val) {
      q.pop_back();
    }
    q.push_back(val);
  }
  void pop(long long val) {
    if (!q.empty() && q.front() == val) q.pop_front();
  }
};
long long powM(long long a, long long b, long long mod) {
  if (b == 1) {
    return a;
  }
  long long A = (a * a) % mod;
  long long ans = powM(A, b / 2, mod);
  if (b % 2 == 1) {
    ans *= a;
    ans %= mod;
  }
  return ans;
}
long long bs(long long x, vector<pair<long long, long long>> &arr) {
  long long l = 0;
  long long r = arr.size() - 1;
  while (l < r) {
    long long mid = (l + r + 1) / 2;
    if (arr[mid].first > x) {
      r = mid - 1;
    } else {
      l = mid;
    }
  }
  return l;
}
long long dp[50][50][50][50];
long long f(long long lx, long long rx, long long ly, long long ry) {
  if (dp[lx][rx][ly][ry] != -1) {
    return dp[lx][rx][ly][ry];
  }
  long long ans = max(rx - lx, ry - ly) + 1;
  for (int i = lx; i < rx; i++) {
    ans = min(ans, f(lx, i, ly, ry) + f(i + 1, rx, ly, ry));
  }
  for (int i = ly; i < ry; i++) {
    ans = min(ans, f(lx, rx, ly, i) + f(lx, rx, i + 1, ry));
  }
  dp[lx][rx][ly][ry] = ans;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<vector<long long>> matr(n, vector<long long>(n, 0));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      char c;
      cin >> c;
      if (c == '#') {
        matr[i][j] = 1;
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int ii = 0; ii < n; ii++) {
      for (int j = 0; j < n; j++) {
        for (int jj = 0; jj < n; jj++) {
          dp[i][ii][j][jj] = -1;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      dp[i][i][j][j] = matr[i][j];
    }
  }
  cout << f(0, n - 1, 0, n - 1);
  return 0;
}
