题目描述

简单版本和困难版本实际上是不同的问题，因此请完整仔细地阅读两个问题的陈述。两个版本之间的唯一区别是操作。 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可以实现的“#”单元的连通分量的最大可能大小。

样例

6
1 1
.
4 2
..
#.
#.
.#
3 5
.#.#.
..#..
.#.#.
5 5
#...#
....#
#...#
.....
...##
6 6
.#..#.
#..#..
.#...#
#.#.#.
.#.##.
###..#
6 8
..#....#
.####.#.
###.#..#
.##.#.##
.#.##.##
#..##.#.

1
7
11
16
22
36

样例说明

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

来源

Codeforces 1985H2，英文题名 Maximize the Largest Component (Hard Version)。