You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

You are given a N*M grid consisting only the characters '-' and '+'

Lets define a "plus of pluses" shape in a grid as an intersection of a row and a column consisting only character '+' and making a shape which looks like a '+' sign. A plus sign is symmetric to 4 directions. which means a plus sign remains same while rotating it by 90,180,270 and 360 degree.

Size of a "plus of pluses" shape is the number of characters it contains.
for example :-

\(- - + - -\)
\(- - + - -\)
\(+ + + + +\)
\(- - + - -\)
\(- - + - -\)

the grid above contains a plus of plus shape of size 9

\(- - + - -\)
\(- - + - -\)
\(+ + + + +\)
\(- - + - -\)
\(- - - - -\)

the grid above contains a plus of pluses shape of size at max 5

\(- +\)
\(+ -\)

the grid above contains 2 plus of pluses signs of size 1 each

find the largest "plus of pluses" shape in the grid and print the size.

Input

first line takes an integer \(T\) : number of testcases
First line of each testcase takes two integer \(N,M\) : number of row and columns
next \(N\) line and \(M\) column takes input of a grid containing only '-' and '+' characters
\(1 <= T <= 10\)
\(1 <= N,M <= 2000\)

sum of \(N*M\) over all testcase will not exceed \(4*10^6\)
Note: input file is too large, use fast input output methods

Output

One integer, for each test case.

Sample

4
3 3
- - -
- - -
- + -
3 3
- - -
- - -
- - -
3 3
+ + +
+ + +
+ + +
5 6
- + - + - -
+ + + + - +
- + + + + +
+ - + + + -
- + - + - -

1
0
5
9