UVA10349 Antenna Placement

给你一个 $h\times w$ 的点阵图，每一个字符为 `*` 和 `o` 其中一个。 你需要用 $1\times 2$ 或 $2\times 1$ 两种矩形将所有的 `*` 覆盖（可以重叠），问至少需要多少个这样的矩形。

第一行一个整数 $t$，表示有 $t$ 个测试数据。 对于每个测试数据： 第一行两个正整数 $h,w$； 接下来是 $h$ 行 $w$ 列的点阵图。

共 $t$ 行，每行一个非负整数，表示最少需要的矩形数量。

对于 $100\%$ 的数据，保证 $1