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 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
Shubhojeet Chakraborty: 2018-06-19 09:44:45

@morass Is n^2*log(n) not supposed to pass ?
edit: n^2 passes :)

Last edit: 2018-06-19 19:27:56
morass: 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 :/

marcelljason06: 2017-03-19 11:13:24

can you please check my submissions?

morass: 2016-12-25 17:09:10

@singhaljoy: yay, gr8 to hear - GJ ^_^

singhaljoy: 2016-12-24 18:02:18

@morass:Thanx for the advice, I changed my approach, got accepted in first go...

morass: 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

singhaljoy: 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!!!

sjk1397: 2016-12-20 19:51:15

my code for 4th sample shows output as 2 but still 12th test case shows wrong...how??

morass: 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. ^_^

hanstan: 2016-09-13 12:54:32

What is the maximum number of 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