2425: 迷宫

北京地图可以看作是R*C的网格，奥运会期间对有的地方要进行交通管制，有的地方不允许进入，有的地方对离开时的行驶方向有限制：有的只允许走到上下两个相邻的格子，有的只允许走到左右两个相邻的格子，没有的任何限制的地方上下左右四个方向都允许。

现在给你地图的描述，格子的描述如下：

• “+”表示可以向任意方向（上、下、左、右）移动一格；

• “-”表示只能向左右方向移动一格；

• “|”表示只能向上下方向移动一格；

• “*”表示该位置不能到达。

你的任务是计算出从左上角到右下角的最少需要经过的格子数。

输入第一行一个整数t(1<=t=10)表示有t组测试数据。每一组测试数据，第一行一个整数r，第二行一个整数c,表示地图是r行c列的，接下来r行，每行c个字符，每个字符是{+,*,-,|}中的一种。你可以假设左上角不会是“*”。

输出有t行，每行一个整数表示对应测试数据所需的最少格子数，如果到达不了右下角输出-1。

3
2
2
-|
*+
3
5
+||*+
+++|+
**--+
2
3
+*+
+*+

3
7
-1