English version | [ver versão em português]

[PI046] Largest Microbe Colony

Dr. Ross Geller is back in the lab (because paleontology was just too mainstream), and he's currently studying microbial growth in Petri dishes. His objective? Identify the largest microbe colony before it spreads uncontrollably — or worse, before someone (cough, Joey) mistakes it for a snack.

The Petri dish is represented as a 2D grid (a matrix), where each cell contains either a living microbe ('#') or is empty ('.'). A microbe colony is a group of connected '#' cells. Cells are considered connected if they are adjacent horizontally, vertically, or diagonally.

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

The size of a colony is the number of connected '#' cells it contains. In the example above, the colonies have sizes 6 (yellow), 3 (cyan), and 4 (green). The largest colony is the yellow one with 6 microbes.

The Problem

You are given several Petri dish configurations (grids of cells). For each configuration, your task is to compute the size of the largest colony of microbes.

Input

The first line contains an integer N, the number of test cases.

Each test case begins with two integers R and C, representing the number of rows and columns in the Petri dish, respectively. The next R lines contain C characters each, representing the grid cells: '.' for an empty cell and '#' for a living microbe.

Output

For each test case, output a single line with an integer: the size of the largest microbe colony found in that Petri dish.

Constraints

The following limits are guaranteed in all the test cases given as input

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:

Versão em Português | [see english version]

[PI046] Calcular a Maior Colónia de Micróbios

O Dr. Ross Geller está de volta ao laboratório (porque a paleontologia era demasiado mainstream) e agora dedica-se ao estudo do crescimento microbiano em placas de Petri. O seu objetivo? Identificar a maior colónia de micróbios antes que ela se espalhe por todo o laboratório — ou pior, que alguém (cof, Joey) a confunda com comida.

A placa de Petri é representada por uma grelha 2D (ou matriz), onde cada célula pode conter um micróbio vivo ('#') ou estar vazia ('.'). Uma colónia de micróbios é um conjunto de células com '#' que estão ligadas entre si horizontalmente, verticalmente ou diagonalmente.

Por exemplo, a seguinte placa de Petri contém exatamente três colónias de micróbios:

O tamanho de uma colónia é igual ao número de micróbios vivos que a compõem. No exemplo acima, as colónias têm tamanhos 6 (amarela), 3 (azul) e 4 (verde). A maior colónia é a amarela, com 6 micróbios.

O Problema

São-lhe dadas várias configurações de placas de Petri (matrizes de células). Para cada uma, o seu objetivo é determinar o tamanho da maior colónia de micróbios.

Input

A primeira linha da entrada contém um número inteiro N, correspondente ao número de casos de teste.

Cada caso de teste começa com dois inteiros R e C, representando respetivamente o número de linhas e colunas da matriz. Seguem-se R linhas, cada uma com C caracteres, onde '.' representa uma célula vazia e '#' representa um micróbio vivo.

Output

Para cada caso de teste, imprima uma única linha com um número inteiro: o tamanho da maior colónia de micróbios na respetiva placa.

Restrições

Os limites seguintes estão garantidos em todos os casos de teste fornecidos como input.

2
5 7
##.#...
.###...
.....##
.#...##
#.#....
4 4
##.#
...#
#...
..#.

6
2

Nota: o primeiro caso é o apresentado acima na figura. O segundo caso tem três colónias: duas com tamanho 2 (verde e amarelo) e duas com tamanho 1 (azul e laranja). Assim, a maior colónia tem tamanho 2: