codeforces#P1985H2. Maximize the Largest Component (Hard Version)
Maximize the Largest Component (Hard Version)
Description
Easy and hard versions are actually different problems, so read statements of both problems completely and carefully. The only difference between the two versions is the operation.
Alex has a grid with $n$ rows and $m$ columns consisting of '.' and '#' characters. A set of '#' cells forms a connected component if from any cell in this set, it is possible to reach any other cell in this set by only moving to another cell in the set that shares a common side. The size of a connected component is the number of cells in the set.
In one operation, Alex selects any row $r$ ($1 \le r \le n$) and any column $c$ ($1 \le c \le m$), then sets every cell in row $r$ and column $c$ to be '#'. Help Alex find the maximum possible size of the largest connected component of '#' cells that he can achieve after performing the operation at most once.
The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n \cdot m \le 10^6$) — the number of rows and columns of the grid.
The next $n$ lines each contain $m$ characters. Each character is either '.' or '#'.
It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.
For each test case, output a single integer — the maximum possible size of a connected component of '#' cells that Alex can achieve.
Input
The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.
The first line of each test case contains two integers $n$ and $m$ ($1 \le n \cdot m \le 10^6$) — the number of rows and columns of the grid.
The next $n$ lines each contain $m$ characters. Each character is either '.' or '#'.
It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $10^6$.
Output
For each test case, output a single integer — the maximum possible size of a connected component of '#' cells that Alex can achieve.
6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.
1
7
11
16
22
36
Note
In the fourth test case, it is optimal for Alex to set all cells in row $4$ and column $2$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $16$.
In the fifth test case, it is optimal for Alex to set all cells in row $2$ and column $4$ to be '#'. Doing so will lead to the largest connected component of '#' having a size of $22$.