给您一张由 $$$n$$$ 行和 $$$m$$$ 列组成的图片。行从上到下编号为 $$$1$$$ 到 $$$n$$$,列从左到右编号为 $$$1$$$ 到 $$$m$$$。每个单元都被漆成黑色或白色。
你觉得这张图不够有趣。如果一幅画中至少有一个十字架,您就认为它很有趣。十字由一对数字 $$$x$$$ 和 $$$y$$$ 表示,其中 $$$1 \le x \le n$$$ 和 $$$1 \le y \le m$$$,这样 $$$x$$$ 行中的所有单元格和 $$$y$$$ 列中的所有单元格都涂成黑色。
例如,这些图片中的每张都包含十字:
第四张图片包含 4 个十字架:位于 $$$(1, 3)$$$、$$$(1, 5)$$$、$$$(3, 3)$$$ 和 $$$(3, 5)$$$。
以下图像不包含十字:
你有一把画笔和一罐黑色颜料,所以你可以让这幅画变得有趣。每分钟您都可以选择一个白色单元格并将其涂成黑色。
要使生成的图片包含至少一个十字,您至少需要花费多少分钟?
您还需要回答多个独立的查询。
输入
第一行包含一个整数 $$$q$$$ ($$$1 \le q \le 5 \cdot 10^4$$$) — 查询数。
每个查询的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^4$$$, $$$n \cdot m \le 4 \cdot 10^5$$$) — 图片中的行数和列数。
接下来的 $$$n$$$ 行包含 $$$m$$$ 个字符 — '.'如果单元格漆成白色,则为“*”;如果单元格漆成黑色,则为“*”。
保证 $$$\sum n \le 5 \cdot 10^4$$$ 和 $$$\sum n \cdot m \le 4 \cdot 10^5$$$。
输出
打印 $$$q$$$ 行,第 $$$i$$$ 行应包含一个整数 - 第 $$$i$$$ 查询的答案,这是您必须花费的最少分钟数,以便生成的图片至少包含一个十字。
示例
输入 #1
9 5 5 ..*.. ..*.. ***** ..*.. ..*.. 3 4 **** .*.. .*.. 4 3 *** *.. *.. *.. 5 5 ***** *.*.* ***** ..*.* ..*** 1 4 **** 5 5 ..... ..*.. .***. ..*.. ..... 5 3 ... .*. .*. *** .*. 3 3 .*. *.* .*. 4 4 *.** .... *.** *.**
输出 #1
0 0 0 0 0 4 1 1 2
注意
该示例包含上面的所有图片,顺序相同。
前 5 张图片已经包含十字,因此您无需绘制任何内容。
您可以在第$$$6$$$图片上绘制$$$(1, 3)$$$、$$$(3, 1)$$$、$$$(5, 3)$$$和$$$(3, 5)$$$,以在$$$(3, 3)$$$中获得十字。这将花费您 $$$4$$$ 分钟。
您可以在第$$$7$$$张图片上绘制$$$(1, 2)$$$,以在$$$(4, 2)$$$中获得十字。
您可以在第$$$8$$$张图片上绘制$$$(2, 2)$$$,以在$$$(2, 2)$$$中获得十字。例如,您可以绘制 $$$(1, 3)$$$、$$$(3, 1)$$$ 和 $$$(3, 3)$$$ 以获得 $$$(3, 3)$$$ 中的十字,但这将花费您 $$$3$$$ 分钟,而不是 $$$1$$$。
在第$$$9$$$张图片上,您可以在最短的时间内获得 9 个可能的交叉。其中之一是$$$(1, 1)$$$:绘制$$$(1, 2)$$$ 和$$$(2, 1)$$$。