H2. Максимизация наибольшей компоненты (сложная версия)
ограничение по времени на тест
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
7
11
16
22
36
Примечание

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

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