Глобальному аэронавигационному научно-исследовательскому центру была поставлена задача строительства пятого поколения сетей мобильных телефонов в Швеции. Самая яркая причина, по которой они получили работу, - это открытие новой, очень шумоподобной антенны. Он называется 4DAir и поставляется в четырех типах. Каждый тип может передавать и принимать сигналы только в направлении, совмещенном с (слегка перекошенной) широтной и продольной сеткой из-за взаимодействующего электромагнитного поля Земли. Эти четыре типа соответствуют антеннам, работающим в направлениях север, запад, юг и восток соответственно. Ниже приведен пример изображения интересных мест, изображенных двенадцатью маленькими кольцами, и девять антенн 4DAir, изображенных эллипсами, покрывающими их.

Очевидно, что желательно использовать как можно меньше антенн, однако по-прежнему следует обеспечить покрытие для каждого интересующего объекта. Промоделируем задачу следующим образом: пусть A - прямоугольная матрица, описывающая поверхность Швеции, где точка является либо точкой интереса, которая должна быть покрыта хотя бы одной антенной, либо пустым местом. Антенны можно располагать в любом месте матрицы A. Когда антенна помещается в строку r и столбец c, эта точка считается покрытой, но также и одна из соседних точек (c + 1, r), (c, r + 1), (c - 1, r) или (c , r - 1) покрывается в зависимости от типа расположения антенны. Каково наименьшее количество антенн, которыми можно покрыть все точки интереса в матрице A?

Входные данные

Первая строка содержит количество сценариев n. Каждый сценарий начинается со строки, содержащей два натуральных числа h и w (1 < h < 40, 0 < w < 10). Далее задана матрица А из h строк, каждая из которых содержит w символов из набора [*, o]. Символ * обозначает символ интереса, тогда как символ o представляет собой открытое пространство.

Выходные данные

Для каждого сценария в отдельной строке выведите минимальное количество антенн, необходимых для покрытия всех *-элементов в матрице сценария.