Maximum Park Square

You are given a city map represented as a grid of n rows and m columns. Each position in the grid is either a building (represented by the character #) or an empty space (represented by the character .). Your task is to determine the largest integer k such that there exists a contiguous k × k subgrid which consists entirely of empty spaces (.). In mathematical terms, you need to find the maximum k for which there exists a subgrid that satisfies: $$\text{for all } 0 \le i, j < k, \; grid[r+i][c+j] = '.' $$

for some starting indices r and c.

If no such subgrid exists, output 0.

inputFormat

The first line contains an integer t representing the number of test cases. For each test case, the first line contains two integers n and m, representing the number of rows and columns of the city map. The following n lines each contain a string of length m consisting of characters # and ., representing the city map.

Example:

4
3 3
###
.#.
###
3 4
....
.#..
....
5 5
.....
.....
.###.
.....
.....
2 2
##
##

outputFormat

For each test case, output a single line containing the maximum integer k such that there exists a k × k subgrid full of empty spaces. If no such subgrid exists, output 0.

Corresponding to the sample input above, the output would be:

1
2
2
0

## sample

4
3 3
###
.#.
###
3 4
....
.#..
....
5 5
.....
.....
.###.
.....
.....
2 2
##
##

1
2
2
0

</p>