New House

Interview

Time limit2sMemory limit512 MB

Summary

Given an N by N grid of free cells and obstacles, find the side length of the largest square made only of free cells.

Level: Easy3 of 10
Topics: Matrix, Dynamic programming, Brute force
Solved: No attempts yet

Problem

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 fits 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 is either '.' (free area) or '#' (obstacle). Your house should be built on free area.

Output

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

Examples1

Example 1

Input

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

Expected output

3
2