【问题描述】

北京地图可以看作是$R*C$的网格，奥运会期间对有的地方要进行交通管制，有的地方不允许进入，有的地方对离开时的行驶方向有限制：有的只允许走到上下两个相邻的格子，有的只允许走到左右两个相邻的格子，没有的任何限制的地方上下左右四个方向都允许。 现在给你地图的描述，格子的描述如下： ●“+”表示可以向任意方向（上、下、左、右）移动一格； ●“-”表示只能向左右方向移动一格； ●“|”表示只能向上下方向移动一格； ●“*”表示该位置不能到达。 你的任务是计算出从左上角到右下角的最少需要经过的格子数。

【输入】

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

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

【输出】

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

3
7
-1