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>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Jenish
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        FRectanglePainting1 solver = new FRectanglePainting1();
        solver.solve(1, in, out);
        out.close();
    }

    static class FRectanglePainting1 {
        long[][][][] dp;
        int[][] arr;

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            dp = new long[n + 1][n + 1][n + 1][n + 1];
            for (int i = 0; i < n + 1; i++)
                for (int j = 0; j < n + 1; j++)
                    for (int k = 0; k < n + 1; k++)
                        for (int l = 0; l < n + 1; l++)
                            dp[i][j][k][l] = -1;


            arr = new int[n + 1][n + 1];

            for (int i = 1; i <= n; i++) {
                char a[] = in.scanString().toCharArray();
                for (int j = 1; j <= n; j++) {
                    arr[i][j] = (a[j - 1] == '#') ? 1 : 0;
                }
            }

            out.println(findit(1, 1, n, n));
        }

        long findit(int x1, int y1, int x2, int y2) {
            if (dp[x1][y1][x2][y2] != -1) return dp[x1][y1][x2][y2];
            if (x1 == x2 && y1 == y2) return dp[x1][y1][x2][y2] = arr[x1][y1];
            long ans = Math.max(x2 - x1 + 1, y2 - y1 + 1);
            for (int i = x1; i < x2; i++) ans = Math.min(ans, findit(x1, y1, i, y2) + findit(i + 1, y1, x2, y2));
            for (int i = y1; i < y2; i++) ans = Math.min(ans, findit(x1, y1, x2, i) + findit(x1, i + 1, x2, y2));
            return dp[x1][y1][x2][y2] = ans;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int INDEX;
        private BufferedInputStream in;
        private int TOTAL;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (INDEX >= TOTAL) {
                INDEX = 0;
                try {
                    TOTAL = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (TOTAL <= 0) return -1;
            }
            return buf[INDEX++];
        }

        public int scanInt() {
            int I = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    I *= 10;
                    I += n - '0';
                    n = scan();
                }
            }
            return neg * I;
        }

        public String scanString() {
            int c = scan();
            while (isWhiteSpace(c)) c = scan();
            StringBuilder RESULT = new StringBuilder();
            do {
                RESULT.appendCodePoint(c);
                c = scan();
            } while (!isWhiteSpace(c));
            return RESULT.toString();
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

