## Problem S3: Maze

In order to make a few dollars, you have decided to become part of a scientific experiment. You are fed lots of pizza, then more pizza and then you are asked to find your way across the city on a scooter powered only by pizza. Of course, the city has lots of intersections, and these intersections are very controlled. Some intersections are forbidden for you to enter; some only let you move north/south as you leave the intersection; others let you move only east/west as you leave the intersection; and the rest let you go in any compass direction (north, south, east or west). Thankfully your scientific friends have given you a map of the city (on the back of a pizza box), with an arrangement of symbols indicating how you can move around the city. Specifically, there are 4 different symbols on the box:

• The symbol `+` indicates we can move in any direction (north/south/east/west) from this location.
• The symbol `-` indicates we can move only east or west from this location.
• The symbol `|` indicates we can move only north or south from this location.
• The symbol `*` indicates we cannot occupy this location.

Your task is to determine how many intersections you must pass through to move from the northwest corner of the city to the south-east corner of the city.

### Input

The input begins with a number t (1 ≤ t ≤ 10) on its own line, which indicates how many different cases are contained in this file. Each case begins with a number r on one line, followed by a number c on the next line (1 ≤ r, c ≤ 20). The next r lines contain c characters, where each character is one of {`+, *, -, |`}. You may assume the north-west corner of the city can be occupied (i.e., it will not be marked with *).

### Output

The output will be t lines long, with one integer per line. The integer on line i (1 ≤ it) indicates the minimum number of intersections required to pass through as you move from the north-west corner of the city to the south-east corner of the city. If there is no way to get from the north-west corner to the south-east corner, output -1 for that test case.

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

### Sample Output

```3
7
-1```

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

• (1/2)
for this question does it the last char(south-east corner) have to be '+' if its anything else does it still work?
also is it possible for it to be '*'?

• (3/1)
 The symbol + indicates we can move in any direction (north/south/east/west) from this location. The symbol - indicates we can move only east or west from this location. The symbol | indicates we can move only north or south from this location. The symbol * indicates we cannot occupy this location.

+, - and | only limits where we can move from that location,
* limits whether or not we can occupy (move to) that location.
So to answer your question directly, it will not work if it is '*', but anything else is fine.

• (0/1)
So you mean that if the starting position is a *, it will not work?

• (2/0)
From the input format,
 You may assume the north-west corner of the city can be occupied (i.e., it will not be marked with *).