H2. 最大化最大连通分量（困难版）

• 时间限制：每个测试点 $2$ 秒
• 内存限制：每个测试点 $512$ 兆字节

简单版和困难版实际上是不同的问题，因此请完整仔细地阅读两个版本的题目描述。两个版本之间的唯一区别在于操作。

Alex 有一个包含 $n$ 行 $m$ 列的网格，由字符 . 和 # 组成。若一组 # 单元格中的任意一个单元格可以通过移动到与该单元格共享一条边的另一个属于该集合的单元格而到达该集合中的任意其他单元格，则称这组 # 单元格形成一个连通分量。连通分量的大小是该集合中单元格的数量。

在一次操作中，Alex 选择任意一行 $r$（$1 \le r \le n$）和任意一列 $c$（$1 \le c \le m$），然后将第 $r$ 行和第 $c$ 列中的所有单元格都设置为 #。请帮助 Alex 找出在至多执行一次操作后，他能得到的最大可能的 # 单元格连通分量的大小。

输入

第一行包含一个整数 $t$（$1 \le t \le 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$。