```go
package main

import (
	"bufio"
	"fmt"
	"os"
)

var memo [50][50][50][50]int
var grid []string
var pref [51][51]int

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func solve(r1, r2, c1, c2 int) int {
	if memo[r1][r2][c1][c2] != 0 {
		return memo[r1][r2][c1][c2] - 1
	}

	cnt := pref[r2+1][c2+1] - pref[r1][c2+1] - pref[r2+1][c1] + pref[r1][c1]
	if cnt == 0 {
		return 0
	}

	if r1 == r2 && c1 == c2 {
		memo[r1][r2][c1][c2] = 2
		return 1
	}

	res := max(r2-r1+1, c2-c1+1)

	for r := r1; r < r2; r++ {
		res = min(res, solve(r1, r, c1, c2)+solve(r+1, r2, c1, c2))
	}
	for c := c1; c < c2; c++ {
		res = min(res, solve(r1, r2, c1, c)+solve(r1, r2, c+1, c2))
	}

	memo[r1][r2][c1][c2] = res + 1
	return res
}

func main() {
	reader := bufio.NewReader(os.Stdin)
	var n int
	if _, err := fmt.Fscan(reader, &n); err != nil {
		return
	}
	
	grid = make([]string, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(reader, &grid[i])
		for j := 0; j < n; j++ {
			val := 0
			if grid[i][j] == '#' {
				val = 1
			}
			pref[i+1][j+1] = pref[i][j+1] + pref[i+1][j] - pref[i][j] + val
		}
	}
	
	fmt.Println(solve(0, n-1, 0, n-1))
}
```