Вам задана картинка, состоящая из \(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\) строк, \(i\)-я строка должна содержать одно число — ответ на \(i\)-й запрос, который равен минимальному количеству минут, которое вам необходимо потратить, чтобы в результате картинка стала содержать хотя бы один крест.
Примечание
Пример содержит все картинки из условия в том же порядке.
Первые 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)\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|