Ada the Ladybug has decided to move to other city. She was deciding where to live - she wanted the city which would be the biggest PLUS to live in. You will be given a map with N×N cities. Size of PLUS is the number of cities in each of four direction (+ the city itself).

Input

The first line contains T, the number of test-cases.

The first line of each test-case will contain 0 < N ≤ 2000 , the size of map.

N lines will follow, each containing N characters. Characters will be either '#' (indicating a city) or '.' (indicating free space).

Output

For each test-case, print exactly one number - the size of biggest '+' (PLUS).

Example Input

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

Example Output

3
1
2
2

Explanation of test-cases

1st test-case

..#..
..#.#
#####
..#.#
..#..

2nd test-case

..#
#.#
#.#

3rd test-case

##.#
####
##.#
#..#

4th test-case

####
####
####
####