Practice on Toph

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

The Game of Rocks

Limits: 500ms, 512 MB

Alice and Bob have come up with a new game.

Bob gives Alice a NxM grid that contains N rows and M columns. Each cell of this grid is either empty or it contains a rock. To win this game, Alice has to choose a rectangle with the highest perimeter enclosed by rocks. The sides of this rectangle has to be axis parallel. The rectangle has to enclose a positive area. If there are multiple such rectangles, Alice has to choose one with the maximum area enclosed by the rocks (See the sample I/O for more detail).

Can you help Alice win this game?

Input

First line of the input contains an integer: T, the number of test cases.

First line of each test case contains two integers: N and M.

The next N lines describe the grid Bob provides. Each line contains M characters. Each character is a *(asterisk) or a .(dot) , where *(asterisk) represents a rock and .(dot) represents an empty cell.

Constraints:
  • 1 <= T <= 10

  • 1 <= N, M <= 200

Output

For each case, print two space separated integers on a separate line: the maximum perimeter and the maximum area enclosed by such a rectangle.

If no rectangle can be formed that encloses a positive area, you must output “No solution” without the quotes.

Samples

InputOutput
4
3 3
***
*.*
***
2 3
***
***
3 3
*.*
*.*
***
6 8
*.....**
***...**
********
*.*.*.**
*.*.****
***.****
8 1
No solution
No solution
12 4

Explanation:

In the first case, there is only one valid rectangle which has length = width = 3. Thus, perimeter = 2(3+3)-4 = 8. It bounds an area of size 1.

In the second case, there is no rectangle that encloses a positive area. Thus there is no solution.

In the third case, there is no valid rectangle. A rectangle must be enclosed by rocks only. Thus there is no solution.

In the fourth case, there are two candidate valid rectangles that we can choose from (enclosed by rocks, enclose a positive area and have the maximum possible perimeter). The maximum area enclosed by these rectangles is 4 (Notice that it does not matter if there is any rock inside the rectangle or not.)

Author
  • Labib666's Avatar

    Labib666

    Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms.
Discussion
Submit

Login to submit