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

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

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

hide comments
2018-06-19 09:44:45 Shubhojeet Chakraborty
@morass Is n^2*log(n) not supposed to pass ?
edit: n^2 passes :)

Last edit: 2018-06-19 19:27:56
2017-03-21 15:55:31
@marcelljason06: This doesn't repair it - yet at least the function seems to be returning some undefined values sometime (i.e. it sometimes reaches the end of function - and there is no return or something)

Also char* is not scaned with "&" but guess thats just detail :)

But I don't know how it shall work - so .. no clue how to behave futher :/
2017-03-19 11:13:24
can you please check my submissions?
2016-12-25 17:09:10
@singhaljoy: yay, gr8 to hear - GJ ^_^
2016-12-24 18:02:18
@morass:Thanx for the advice, I changed my approach, got accepted in first go...
2016-12-23 16:23:06
@singhaljoy: Firstly - you have "WA" on test-case "1", not "12" .. secondly don't think the problem is in a "corner" test-case but handling multiple test-cases

Good Luck & Have Nice Day
2016-12-23 01:59:46
@morass:I am getting WA for case 12 i rechecked all corner cases i can think of, so please check the 12th case!!!
2016-12-20 19:51:15
my code for 4th sample shows output as 2 but still 12th test case shows wrong...how??
2016-09-13 14:51:35
@hanstan: Hello, the maximum is 100, anyway this information might be slightly "misleading", because the number of test-cases depends on sizes of maps. ^_^
2016-09-13 12:54:32 hanstan
What is the maximum number of test cases?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.