ACM-ICPC INC 2009

Problem F

New House

Time Limit: 3s

Johan wants to build a new house and he wants his house as large as it can. Given an N x N grid land, find the largest square size that fit in the free area.

Input

The first line of input contains an integer T, the number of test cases follow.

Each test case starts with an integer N (1 <= N <= 10) denoting the size of the grid land. The next N lines each contains N characters. Each character be either '.' (free area) or '#' (obstacle). Your house should be build on free area.

Output

For each test case, output in a line the size of the largest square on free area.

Sample InputOutput for Sample Input
2
10
..........
.#####....
..#..###..
...##.....
...#..#...
...#...###
....######
..........
##########
#########.
5
##..#
....#
.#..#
####.
.#..#

3
2