Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

H1. Максимизация наибольшей компоненты (простая версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Простая и сложная версии фактически представляют собой разные задачи, поэтому внимательно прочитайте условия обеих задач. Единственное различие между двумя версиями — это применяемая операция.

У Алекса есть матрица из $$$n$$$ строк и $$$m$$$ столбцов, состоящая из символов '.' и '#'. Набор '#' ячеек формирует компоненту связности, если из любой ячейки в этом наборе можно достичь любую другую ячейку в этом наборе, перемещаясь только в другую ячейку набора, которая имеет общую сторону. Размер компоненты связности — это количество ячеек в наборе.

За одну операцию Алекс выбирает любую строку $$$r$$$ ($$$1 \le r \le n$$$) или любой столбец $$$c$$$ ($$$1 \le c \le m$$$), затем устанавливает каждую ячейку в строке $$$r$$$ или столбце $$$c$$$ равной '#'. Помогите Алексу найти максимально возможный размер наибольшей компоненты связности из ячеек '#', который он может достичь после выполнения операции не более одного раза.

Входные данные

Первая строка ввода содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — количество строк и столбцов матрицы.

Следующие $$$n$$$ строк содержат по $$$m$$$ символов. Каждый символ может быть '.' или '#'.

Гарантируется, что сумма $$$n \cdot m$$$ по всем наборам не превышает $$$10^6$$$.

Выходные данные

Для каждого теста выведите одно целое число — максимально возможный размер компоненты связности из ячеек '#', который может достичь Алекс.

Пример
Входные данные
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
Выходные данные
1
6
9
11
15
30
Примечание

Во втором примере для Алекса оптимально установить все ячейки в столбце $$$2$$$ равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер $$$6$$$.

В третьем примере для Алекса оптимально установить все ячейки в строке $$$2$$$ равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер $$$9$$$.

В четвертом примере для Алекса оптимально установить все ячейки в строке $$$4$$$ равными '#'. Это приведет к тому, что наибольшая компонента связности из '#' будет иметь размер $$$11$$$.