题目描述

全球航空研究中心承担了在瑞典建设第五代移动电话网络的任务。他们获得该任务的一个重要原因是发现了一种名为4DAir的新型高抗噪天线，共有四种类型。由于地球电磁场的相互作用，每种类型的天线只能在与（略微倾斜的）经纬度网格对齐的方向上传输和接收信号。这四种类型分别对应向北、向西、向南和向东方向工作的天线。下图展示了一个示例：12个小圆圈表示兴趣点，9个椭圆表示覆盖这些点的4DAir天线。

显然，我们希望使用尽可能少的天线覆盖所有兴趣点。我们将问题建模如下：设矩阵$A$描述瑞典的表面，其中每个元素要么是必须被至少一个天线覆盖的兴趣点（用'*'表示），要么是空白区域（用'o'表示）。天线只能放置在矩阵的某个元素位置上。当在行列$(r, c)$放置一个天线时，该位置被覆盖，并且根据所选天线类型，其相邻的四个位置之一（$(c+1,r)$、$(c,r+1)$、$(c-1,r)$或$(c,r-1)$）也会被覆盖。问题转化为：找到一种天线放置方案，使得所有兴趣点都被覆盖，且使用的天线数量最少。

输入

输入第一行包含一个正整数$n$，表示测试用例的数量。每个测试用例以两个正整数$h$和$w$开始（$1 \leq h \leq 40$，$0 < w \leq 10$），接下来是一个$h$行$w$列的矩阵，每行由字符''和'o'组成，''表示兴趣点，'o'表示空白区域。

输出

对于每个测试用例，输出覆盖所有'*'所需的最小天线数量，每个结果占一行。

输入数据示例 1

2  
7 9  
ooo**oooo  
**oo*ooo*  
o*oo**o**  
ooooooooo  
*******oo  
o*o*oo*oo  
*******oo  
10 1  
*  
*  
*  
o  
*  
*  
*  
*  
*  
*  

输出数据示例 1

17  
5  

来源

Svenskt Mästerskap i Programmering/Norgesmesterskapet 2001