Вам задана картинка, состоящая из $$$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$$$-й запрос, который равен минимальному количеству минут, которое вам необходимо потратить, чтобы в результате картинка стала содержать хотя бы один крест.
9 5 5 ..*.. ..*.. ***** ..*.. ..*.. 3 4 **** .*.. .*.. 4 3 *** *.. *.. *.. 5 5 ***** *.*.* ***** ..*.* ..*** 1 4 **** 5 5 ..... ..*.. .***. ..*.. ..... 5 3 ... .*. .*. *** .*. 3 3 .*. *.* .*. 4 4 *.** .... *.** *.**
0 0 0 0 0 4 1 1 2
Пример содержит все картинки из условия в том же порядке.
Первые 5 изображений уже содержат кресты, а потому вам не нужно ничего перекрашивать.
Вы можете перекрасить $$$(1, 3)$$$, $$$(3, 1)$$$, $$$(5, 3)$$$ и $$$(3, 5)$$$ на $$$6$$$-й картинке, чтобы получить крест в $$$(3, 3)$$$. Это займет у вас $$$4$$$ минуты.
Вы можете перекрасить $$$(1, 2)$$$ на $$$7$$$-м изображении, чтобы получить крест в $$$(4, 2)$$$.
Вы можете перекрасить $$$(2, 2)$$$ на $$$8$$$-й картинке, чтобы получить крест в $$$(2, 2)$$$. Либо же вы можете закрасить $$$(1, 3)$$$, $$$(3, 1)$$$ и $$$(3, 3)$$$ для креста в $$$(3, 3)$$$, но это займет $$$3$$$ минуты против $$$1$$$-й в первом варианте.
На $$$9$$$-й картинке мы можете получить за минимальное время один из 9 крестов. Например, в $$$(1, 1)$$$: понадобится закрасить $$$(1, 2)$$$ и $$$(2, 1)$$$.
