Descripción

Johan quiere construir una nueva casa, y la quiere tan grande como se pueda. Dado un terreno reticular de tamaño ~N x N~, halle el mayor cuadrado que pueda ser ubicado en el área libre del terreno.

Especificación de entrada

La primera línea de la entrada contiene un entero ~T (1 <= T <= 100)~, que representa la cantidad de casos de prueba que le siguen. Cada caso de prueba comienza con un entero ~N <= 10~ que denota el tamaño del terreno reticular. Las próximas ~N~ líneas contienen ~N~ caracteres. Cada caracter será un punto ('.'), que representa un área libre, o un numeral ('#'), que representará un área ocupada. La casa se debe construir en el área libre.

Especificación de salida

Para cada caso de prueba, imprima en una línea aparte el tamaño del mayor cuadrado que se pueda construir en el área libre.

Ejemplo de entrada

2
10
..........
.#####....
..#..###..
...##.....
...#..#...
...#...###
....######
..........
##########
#########.
5
##..#
....#
.#..#
####.
.#..#

Ejemplo de salida

3
2