You will need to figure out the best way to install an Ethernet cable in your house, connecting two wall sockets.

The rooms in your apartment are 3m high. There are doorways that are 2m high and 1m wide. The wall sockets are at the floor level (0m).

You can install the cable horizontally or vertically along the walls (at any height), across the ceiling in north–south or east–west direction, and through doorways (at any height). However, you cannot have the cable running across the floor, you definitely don't want to have the cable hanging in the air, you can't make holes in the walls, and you can't install the cable e.g. at a 45° angle.

You have got the floorplan of your apartment in a convenient machine-readable ASCII-art format (with all walls conveniently measuring some multiple of 1m), and you would like to automatically find the shortest route.

We will ignore things like the thickness of the walls, thickness of the cable, and the curvature of the cable, so you can assume that the walls are 0m thick, and the cable can make sharp 90° angles.

Input

The first input line contains an integer t: the number of test cases. Then there are t test cases, described as follows:

The first line contains two integers w and h: the width and the height of the grid. Then there are two lines of the form "x y d" that describe the cable starting point and endpoint: (x,y) is the location of the point (0 \le x \le w and 0 \le y \le h), and d is the direction ("north", "east", "south", or "west"). The origin is in the upper left corner, x coordinates increase east (right), and y coordinates increase south (down).

Finally, there are 2h+1 lines, each with 2w+1 characters, that describe the floorplan. In the floorplan, there are regular markers "+" at every second position on every second line. Between a pair of "+" markers, the following codes may occur: "-" or "|" to indicate wall segments (we use different markers for horizontal and vertical segments), and "D" to indicate doorways (we use the same marker for horizontal and vertical doorways). The rest of the map is filled with ".".

Doorways are always surrounded by regular wall segments. Cable will always start and end in the middle of a wall, between two wall segments.

Output

For each test case, output one integer: the length of the shortest cable that connects the starting point and endpoint (in meters).

Limits

• 1 \le t \le 50
• 1 \le w,h \le 50

Example

Input:

1
7 8
0 6 east
2 3 east
+-+-+-+-+-+-+-+
|...|.........|
+.+.+.+.+.+.+.+
|...|.........|
+.+.+.+.+.+.+.+
|...|.........|
+.+.+.+.+.+.+.+
|...|.........|
+.+.+-+D+-+-+-+
|.............|
+.+.+.+.+.+.+.+
|.............|
+.+.+.+.+.+.+.+
|.............|
+.+.+.+.+.+.+.+
|.............|
+-+-+-+-+-+-+-+

Output:

13

The following figure shows the rooms in the example apartment, as well as an optimal way to install the cable: