410005 - 天线

如图10.12所示，电信公司给城市安装新型无线网络，一个无线网络最多可以覆盖网格上垂直或水平相邻的两座城市，问覆盖所有城市最少要用多少无线网络。

第一行为一个整数n，表示测试数据组数，每组数据第一行为两个整数h和w（1≤h≤40，0＜w≤10），表示矩阵的高和宽。 随后h行，描述矩阵，其中“*”表示城市，“o”表示空地。

输出最少安装天线数。