{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Вам дана 2D доска, на которой в некоторых ячейках есть золото. Вы хотите заполнить доску **2 x 1** домино так, чтобы все золото было покрыто. Вы можете использовать домино вертикально или горизонтально, и домино могут перекрываться. Все, что вам нужно сделать, это покрыть золото наименьшим количеством домино.\n\n![Gold Grid](CDN_BASE_URL/89e4824aff599d73f3dc66bb4e6823c7?v\u003d1709572888)\n\t\nНа картинке золотые ячейки обозначают, что в них есть золото, а синие - **2 x 1** домино. Домино могут перекрываться, как мы уже сказали, как показано на картинке. На самом деле домино покроют полностью **2 x 1** ячейки; мы показали маленькие домино только для того, чтобы показать, как покрыть золото 11 домино."}},{"title":"Ввод","value":{"format":"MD","content":"Ввод начинается с целого числа **T (\u0026le; 50)**, обозначающего количество тестов.\n\nКаждый тест начинается с строкой, содержащей два целых числа **m (1 \u0026le; m \u0026le; 20)** и **n (1 \u0026le; n \u0026le; 20)** и **m \\* n \u0026gt; 1**. Здесь **m** представляет количество строк, а **n** представляет количество столбцов. Затем будет **m** строк, каждая содержащая **n** символов из набора `[*, o]`. Символ `*` обозначает ячейки, содержащие золото, а символ `o` представляет пустые ячейки."}},{"title":"Вывод","value":{"format":"MD","content":"Для каждого теста выведите номер теста и минимальное количество домино, необходимых для покрытия всего золота (`*` ячейки) на данной доске."}},{"title":"Пример","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2\n5 8\noo**oooo\n*oo*ooo*\n******oo\n*o*oo*oo\n******oo\n3 4\n**oo\n**oo\n*oo*\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 11\nCase 2: 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}