Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Meena And Her Dream

By TheDarkKnight · Limits 1s, 1.5 GB

We are now in meena’s dream. But she can’t see us, we are invisible for her, but she just can hear the whisper of ours. She is been captured by demon in her sleep . In her sleep she is in big room. She already understood the floor is formed of three color tiles- white, blue and green. She has a map which describes the tiles’ colors in the room. She can see from the map that the room is a grid having m rows and n columns

Now, if she wants to be freed from demon she must find an axis parallel quadrilateral in the floor, where all the tiles are of same color, they/it must form a certain regular polygon shape,where all the sides of the polygon are equal, their inner angles are equal, their largest diagonals are equal And they are perpendicular to each other. “And they follow recursive property of shape symmetry”.

We need to find the value of the area of this type of special polygon shape and whisper to her. But there can be many such areas, so we need to find the largest area among those which are of this shape. Because if she can know this area and say it three times, she will magically reach there and be freed. Can you free her ?

Input

Input consists of multiple test cases. At the beginning of the input, there is a test number T (1 ≤ T ≤ 1000).

After that there will be T test cases. At the beginning of each test case. There are two number m, n(1 ≤ m,n ≤ 100) in one line separated by space. After that there will be m lines each containing n characters.The characters will be either “w”, “g” , “b” ( except the inverted comma). They define the tiles orientation.

m = number of tiles row in the room

n = number of tiles in each column

A input in the ith line (1 ≤ i ≤ m) and in jth column (1≤ j ≤ n) if ‘w’ ,

it means there is a white color tile in the ith row of tiles and in the jth column. Similarly for ‘g’ represents green color tiles and ‘b’ represents blue color tiles.

Output

Output an integer for each test case, in separate lines, indicating the answer to that case.

Sample

InputOutput
7
4 3
www
ggg
ggg
ggg
4 4
wwww
gbbg
gbbg
gbbg
3 3
www
wbb
wbb
3 4
gggb
bbbb
wwwb
5 9
wwwwbbbbb
wwwwbbbbb
wwwwbbbbb
wwwwbbbbb
ggggbbbbb
5 11
wbbbbwwwwbb
bbbbbwwwwbb
bbbbbggggbb
bbbbbggggbb
bbbbbbbbbbb
5 24
wwbwwgwbwwgbbbbgbwwwbbbb
wwbwwgbwbwgwbbwgbwwwbwww
wwbwwgbbbwgwbbwgbwwwbbbw
wwbbbgbwbwgwbbwgbwwwbwww
wwbbbgbwbwgwbbwgbwwwbbbb 
9
4
4
1
25
16
9

We simulate the sixth case, here the polygon shape which satisfies all the condition is a square and the largest area is found in consisting of (2,1), (2,2),(2,3),(2,4),(3,1),(3,2),(3,3),(3,4),(4,1),(4,2),(4,3),(4,4),(5,1),(5,2),(5,3),(5,4) these cells.

Discussion

Statistics


74% Solution Ratio

IamHotEarliest, Aug '17

arnob_daFastest, 0.1s

fsshakkhorLightest, 131 kB

rebornShortest, 635B

Submit

Login to submit