Maze

Interview

Time limit1sMemory limit128 MB

Summary

Find the shortest path in a grid where each cell dictates which directions you may exit, counting cells visited.

Level: Medium4 of 10
Topics: BFS, Graph, Matrix
Solved: No attempts yet

Problem

To earn a bit of money, you have signed up for a scientific experiment. You are fed a lot of pizza, and then asked to ride a scooter — powered only by pizza — across the city to a destination.

The city is a grid of intersections, and each intersection has its own movement rule. Every cell of the map is marked with one of four symbols:

+ : from this cell you may leave in any direction (north, south, east, or west).
- : from this cell you may leave only to the east or west.
| : from this cell you may leave only to the north or south.
* : this cell cannot be entered.

Each symbol describes the directions in which you may leave that cell. Starting from the north-west corner of the city (the top-left cell) and travelling to the south-east corner (the bottom-right cell), determine the minimum number of intersections you must pass through, counting both the starting cell and the destination cell.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 10$ ).

Each test case begins with the number of rows $r$ on one line, followed by the number of columns $c$ on the next line ( $1 \le r, c \le 20$ ). The next $r$ lines each contain $c$ characters, where every character is one of +, -, |, *. The north-west corner cell is guaranteed to be enterable (it is never *).

Output

Print one integer per test case, on its own line. Line $i$ contains the minimum number of intersections you must pass through to travel from the north-west corner to the south-east corner in test case $i$ . If there is no way to reach the south-east corner from the north-west corner, print $-1$ for that test case.

Examples3

Example 1

Input

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

Expected output

3
7
-1

Example 2
Input
```
1
1
1
+
```
Expected output
```
1
```
Example 3
Input
```
1
1
5
+++++
```
Expected output
```
5
```