In what concerns the continuous evaluation solving exercises grade during the semester, you should submit until 23:59 of April 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 #06 exercise sheet]


In this problem you should submit a complete program with the main function, reading with functions such as scanf and printing with functions such as printf.

[PII042] Wait, Is That Microbe Moving?

Dr. Ross Geller is back in the lab (because paleontology was just too mainstream), and he's studying microbial growth in a Petri dish. His goal? Find the largest microbe colony before it spreads all over his workspace — and more importantly, before someone (cough, Joey) mistakes it for food.

The Petri dish can be thought of as a 2D grid, i.e. a matrix, where each cell may be either living microbe ('#') or an empty space ('.'). A microbe colony consists of connected '#' cells that are adjacent horizontally, vertically or diagonally.

For example, the following Petri dish has exactly three microbe colonies:

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

The size of a colony is equal to the number of living microbes that make it up. In the picture above, the 3 colonies have size 6 (the yellow one), 3 (the blue one) and 4 (the green one). The largest colony is the one with the largest size, which in this case is the yellow colony.

The Problem

Given the state of several cultures of microbes (indicated by a matrix of cells) your task is to find out the size of the largest microbe colony in each of them, i.e. the size of the largest connected set of living microbes in each case.

Input

On the first line there is an integer N indicating the amount of cases to consider.

Each case starts with two numbers R and C indicating respectively the number of rows and columns of the petri dish. The R lines follow, each one with C characters, indicating the contents of each position: '.' for an empty position and '#' for a position with a living microbe.

Output

The output should have N lines, each one with the size of the correspondent largest colony of microbes.

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       Dimensions of the matrix

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

Note: the first case is the one above in the figure. The second case has three colonies: two of size 2 (green and yellow) and two of size 1 (blue and orange). Therefore, the largest colony has size 2:

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

 


Programming II (CCINF1002)
DCC/FCUP - University of Porto