In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of December 14th
(this exercise will still be available for submission after that deadline, but without couting towards your grade)
[to understand the context of this problem, you should read the class #09 exercise sheet]


[AED056] Counting Cells

Mary has a biology lab assignment and she needs your help. She is growing small microbes in a Petri dish and needs to look at them under a microscope to see which is the largest visible microbe.

The Petri dish can be thought of as a 2D grid, that is, a matrix, where at each position there may or may not be a cell. Two cells are connected if they are adjacent vertically, horizontally or diagonally. A microbe is a collection of connected cells. For example, the following Petri dish has exactly three microbes (‘.’ is an empty position, ‘#’ is a position with a cell):

# # . # . . .
. # # # . . .
. . . . . # #
. # . . . # #
# . # . . . .

The size of a microbe is equal to the number of cells that make it up. In the picture above, the 3 microbes are 6 (the yellow one), 3 (the blue one) and 4 (the green one). The largest microbe is the one with the largest size. In this case, the largest microbe is the yellow one.

The Problem

Given the state of several cultures of microbes (indicated by a matrix of cells) your task is to find out the number of microbes and the size of the largest microbe in each of them, that is, the number of connected sets of cells and the size of the largest one in each case.

Input

The first line of the input contains a number N indicating the number of cases to consider.

Each of the cases begins with two numbers R and C indicating respectively the number of rows and columns of the Petri dish to be considered, followed by R lines, each with C characters, indicating the content of each position: ‘.’ for an empty position and ‘#’ for a position with a cell.

Output

The output should consist of N lines, one for each input case. Each one should have two numbers separated by a single space: the number of microbes and the size of the largest microbe in the corresponding case.

Constraints

The following limits are guaranteed in all the test cases that will be given to your program:

1 ≤ N ≤ 20       Number of test cases
1 ≤ R, C ≤ 100       Number of rows and columns

Example Input Example Output
2
5 7
##.#...
.###...
.....##
.#...##
#.#....
4 4
##.#
...#
#...
..#.
3 6
4 2

Explanation of Example Input

The first case corresponds to the figure in the problem statement with 3 microbes, the largest one (in yellow) with 6 cells.

The second case corresponds to the following figure, with different components indicated in different color and the largest one having 2 cells (green or yellow).

# # . #
. . . #
# . . .
. . # .


Algorithms and Data Structures (L.EIC011) 2024/2025
DCC/FCUP & DEI/FEUP - University of Porto