import numpy as np class Solver(object): def __init__(self): self.max_depth = 0 def puts(self, ind, muki, box, n, depth=0): i = ind // n j = ind % n if box[i, j] != 0: if not ind == n**2-1: self.puts(ind+1, 0, box, n, depth) self.puts(ind+1, 1, box, n, depth) else: new_box = box.copy() new_depth = depth if muki == 0: room = new_box[i:i+n-1, j] else: room = new_box[i, j:j+n-1] if room.sum() >= 1 or room.size != n-1: pass else: room += 1 new_depth = depth + 1 for k in range(ind+1, n**2): self.puts(k, 0, new_box, n, new_depth) self.puts(k, 1, new_box, n, new_depth) if self.max_depth < depth: self.max_depth = depth def solve(self, box, n): self.puts(0, 0, box, n) self.puts(0, 1, box, n) return self.max_depth n = int(input()) box = [] for i in range(n): row = list(input().strip()) row = (np.array(row)=='#').astype('i') box.append(row) box = np.array(box) solver = Solver() ans = solver.solve(box, n) print(str(ans)+'\n')