CF1985H2 Maximize the Largest Component (Hard Version)

简单版本和困难版本实际上是不同的问题，因此请完整仔细地阅读两个问题的陈述。两个版本之间的唯一区别是操作。 Alex有一个由 $ n $ 行和 $ m $ 列组成的网格，由“.”和“#”字符组成。如果从该组中的任何单元格开始，通过仅移动到该组中共享一个共同边的另一个单元格，就可以到达该组中的任何其他单元格，则一组“#”单元格形成一个连通分量。连通分量的尺寸是该组中的单元格数量。 在一次操作中，Alex选择任意行$ r $（$ 1 \le r \le n $）和任意列$ c $（$ 1 \le c \le m $），然后将行$ r $和列$ c $中的每个单元格设置为“＃”。帮助Alex找到他在最多执行一次操作后，可以实现的“＃”个单元格的最大连通分量的最大可能大小。

输入的第一行包含一个整数 $ t $（$ 1 \leq t \leq 10^4 $）——测试用例的数量。 每个测试用例的第一行包含两个整数$n$和$m$（$1 \le n \cdot m \le 10^6$）——网格的行数和列数。 接下来的 $n$ 行每行包含 $m$ 个字符。每个字符要么是 '.'或 保证所有测试用例中的 $ n \cdot m $ 的总和不超过 $ 10^6 $。

对于每个测试用例，输出一个整数——Alex可以实现的“#”单元的连通分量的最大可能大小。

在第四个测试用例中，Alex将第4行和第2列的所有单元格设置为“#”是最优的。这样做将导致“#”的最大连通分量大小为16。 在第五个测试用例中，Alex将第2行和第4列的所有单元格设置为“#”是最优的。这样做将导致“#”的最大连通分量大小为22。