U511007 地刺大战僵尸

小 K 的花园是一个 $n$ 行 $m$ 列的网格图，初始时上面种植有了一些地刺用来抵挡僵尸的进攻，小 K 开了外挂，僵尸一旦踩到地刺上就会阵亡。 僵尸会从小 K 的花园的右侧进攻：僵尸可以选择第 $m$ 列的任意一个格子出发，它们可以移动到和当前格子有公共边的相邻格子上去。它们想找到一条没有地刺的路径到达花园的最左侧，即只要它们到达了第 $1$ 列，小 K 的脑子就会被僵尸给吃掉。 小 K 可以在网格图上补充地刺。但是，种植地刺的格子之间不能有公共边（不能相邻），现在小 K 想知道他最少种多少个地刺才能抵挡住僵尸的进攻，如果小 K 找不到种植地刺的方法，输出 $-1$。

第一行一个整数 $T$ 表示输入数据的组数。 接下来 $T$ 组数据，每组数据的第一行两个整数 $n,m$ 表示小 K 花园的行数和列数。 接下来 $n$ 行，每行一个长为 $m$ 的字符串，用来表示这一行的地刺种植情况，其中 "." 表示这里是空地，"#" 表示这里种植了一个地刺。

输出 $T$ 行，每行一个整数，表示在该组输入下如果小 K 不能保住他的脑子（失败），输出 $-1$，否则输出小 K 最少需要种植的地刺数量，使得种植完这些地刺之后，僵尸们找不到一条从最右侧到最左侧的路径。

**【数据范围】** - 对于 $100\%$ 的数据，$1 \le T \le 10,1 \le n,m \le 1000$，初始的花园中不会有地刺在相邻格子上，字符仅包含 `.` 和 `#` 两种字符 | 测试点编号 | $n \times m$ | 特殊约束 | | ------------ | ---------------------- | -------- | | $1 \sim 6$ | $n \times m \le 10^6$ | $A$ | | $7 \sim 12$ | $n \times m \le 20$ | 无 | | $13 \sim 20$ | $n \times m \le 10^6 $ | 无 | **【约束条件】** - **【A】** 保证答案为 $0$ 或 $1$。