Largest Square Park

You are given an n x n grid representing a city map where each cell is either empty ('.') or occupied by a building ('#'). Your task is to determine the side length of the largest square park (a contiguous sub-grid) that can be built on empty cells only.

To solve this problem, you can use dynamic programming. Let \(dp[i][j]\) denote the side length of the largest square ending at cell \((i,j)\) that can be formed using only empty cells. The recurrence is given by:

[ dp[i][j] = \begin{cases} 1, & \text{if } i = 0 \text{ or } j = 0 \text{ and } grid[i][j] = '.' \ \min{dp[i-1][j],, dp[i][j-1],, dp[i-1][j-1]} + 1, & \text{if } grid[i][j] = '.' \ 0, & \text{if } grid[i][j] = '#' \end{cases} ]

Your program should read the input from stdin and output the answer to stdout.

inputFormat

The first line contains an integer n representing the size of the grid. The following n lines each contain a string of length n composed of characters '.' (empty cell) and '#' (building).

Example:

5
..##.
.....
##..#
..#..
.....

outputFormat

Output a single integer representing the side length of the largest square park that can be built on the grid using only empty cells.

Example:

2

## sample

5
..##.
.....
##..#
..#..
.....

2