Maximum Non-overlapping Bar Placement

You are given an n x n grid consisting of the characters . and X. Your task is to find the maximum integer k such that you can choose m (with m \le 2) bars of size either 1 x k or k x 1 placed on the grid. Each bar must cover only cells containing . and the bars must not overlap (i.e. share any common cell). Note that you may choose to place just one bar if a placement of two is not possible.

Clarification: In other words, you need to determine the largest k for which there exists at least one contiguous segment of . of length k either horizontally or vertically. (If there is only one such segment, it still satisfies the condition since 1 \le 2.)

Mathematical Note: Let \(L_{max}\) denote the maximum number of consecutive dots in any row or column, then the answer is \(k = L_{max}\) if \(L_{max} > 0\); otherwise, the answer is 0.

inputFormat

The first line of input contains an integer n which denotes the size of the grid. The following n lines each contain a string of length n composed of characters . and X, representing the grid.

It is guaranteed that 1 \le n \le 1000.

outputFormat

Output a single integer, the maximum possible value of k that satisfies the condition described above.

sample

1
.

1