ADAPLUS - Ada and Plus


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 the 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

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

hide comments
morass: 2016-09-12 13:39:45

meettaraviya: I think your solution gets WA earlier. I've added 4th sample (if I executed your program correctly, the output was "3" but it shall be "2")

meettaraviya: 2016-09-12 13:21:34

12th test case seems to be wrong. please check thoroughly

Sarthak Munshi: 2016-09-08 13:20:54

godamn 12th test case . any hints ? ;p

Last edit: 2016-09-08 15:52:30
gomathi ganesan: 2016-09-06 15:38:10

@morass: Understood the test cases.Thanks for your response.

morass: 2016-09-06 11:52:07

@gomathi ganesan: One has to search for biggest PLUS, so for first example, it is on [2][2], for second one it is in any hash and for third one, it is on [1][1]. If you found some "part" unclear, please tell me and I will try to clarify! Thanx, Morass

gomathi ganesan: 2016-09-06 09:07:50

Could anyone explain the test cases?


Added by:Morass
Date:2016-09-05
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU