AT_past20_j グリッドの禁止パターン

There is an $ N \times N $ grid with $ N $ horizontal rows and $ N $ vertical columns. Let $ (i, j) $ denote the cell in the $ i $ -th row from the top and $ j $ -th column from the left. Initially, each cell is painted black or white; cell $ (i, j) $ is painted black if $ S_{i, j} $ is `#`, and white if $ S_{i, j} $ is `.`. You will repeatedly choose one cell to paint black so that the grid satisfies the following condition: - for any cell $ (x, y) $ painted white, at most two of cells $ (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1) $ (except for non-existent ones) are painted black. At least how many operations are required to meet the condition?

The input is given from Standard Input in the following format: > $ N $ $ S_{1, 1} S_{1, 2} \cdots S_{1, N} $ $ S_{2, 1} S_{2, 2} \cdots S_{2, N} $ $ \vdots $ $ S_{N, 1} S_{N, 2} \cdots S_{N, N} $

Print the answer in one line.

### Sample Explanation 1 Cell $ (2, 2) $ is painted white, and all of the four adjacent cells are painted black. By repainting cell $ (2, 2) $ black, the grid satisfies the condition. ### Sample Explanation 2 By repainting cell $ (2, 2) $ black, the grid satisfies the condition. ### Sample Explanation 3 The grid satisfies the condition only when all the white cells are repainted black. ### Constraints - $ 1 \leq N \leq 2000 $ - $ S_{i, j} $ is `.` or `#`.