B. Очередная задача про кресты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задана картинка, состоящая из $$$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)$$$.