U578817 赵老尸大战王の冻

题目传送门 [U511007 地刺大战僵尸](https://www.luogu.com.cn/problem/U511007?contestId=256385) 由于王の冻在课堂上说自己得了NOI金牌，赵老尸非常愤怒，于是决定从教室门发起肘击，肘飞所有课桌，然后拿走王の冻的金牌。王の冻不想失去自己的金牌，于是决定发起金牌保卫战。 **也试试这些题目** - [U79657 王之栋的魔法](https://www.luogu.com.cn/problem/U579657) - [U580277 别样的进步大战](https://www.luogu.com.cn/problem/U580277) - [U609367 二等分的NOI金牌](https://www.luogu.com.cn/problem/U609367)

王の冻的教室是一个 $n$ 行 $m$ 列的网格图，初始时上面种植有了一些学生用来抵挡赵老尸的肘击，学生都是小蒟蒻，写的入门题全WA，所以赵老师走到学生上看到学生写的代码就会被气死。 赵老尸会从王の冻的教室的右侧肘击：赵老尸可以选择第 $m$ 列的任意一个格子出发，它们可以移动到和当前格子有公共边的相邻课桌上去。它们想找到一条没有学生的路径到达教室的最左侧，即只要它们到达了第 $1$ 列，王の冻的NOI金牌就会被赵老尸给吃掉。 王の冻可以在网格图上补充学生。但是，种植学生的格子之间不能有公共边（不能相邻），这会使学生讲悄悄话。现在王の冻想知道他最少种多少个学生才能抵挡住赵老尸的肘击，如果王の冻找不到种植学生来抵挡赵老尸的方法，输出 $-1$。

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

输出 $T$ 行，每行一个整数，表示在该组输入下如果王の冻不能保住他的NOI金牌（失败），输出 $-1$，否则输出王の冻最少需要种植的学生数量，使得种植完这些学生之后，赵老尸们找不到一条从最右侧到最左侧的路径。

**【数据范围】** - 对于 $100\%$ 的数据，$1 \le T \le 10,1 \le n,m \le 1000$，初始的教室中不会有学生在相邻格子上，字符仅包含 `.` 和 `#` 两种字符 **【cinbarhuchの威胁】** - 你小子最好不要让我知道你过不了第10个点