I. Cupcake Factory
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Sally just began her new job as a security guard at the Cupcake Factory! Her first task is to transport a cupcake from one side of the factory to the other.

The Cupcake Factory can be represented by a $$$n \times m$$$ grid. ($$$1 \leq n, m \leq 10^3$$$)

Each cell in the grid contains either nothing, a switch, a conveyor, or a wall. If a cell contains a conveyor, the conveyor may be oriented in any of the four cardinal directions.

Initially, all conveyors are off, and any time Sally visits a cell with a switch, she may decide to turn all conveyors on or off, without taking any time.

At each second, if Sally is standing on a conveyor which is currently on, she must move in the direction that the conveyor is facing, taking one second to move between the two cells. If the cell that Sally would move to is a wall or it is outside of the grid, she will be stuck indefinitely, and cannot move any further. Otherwise, she may move in any of the four cardinal directions as long as the corresponding adjacent cell does not contain a wall and is within the grid. This move will take two seconds.

Sally begins at the top-left cell of the grid, and wants to carry a cupcake to the bottom-right cell of the grid, but the cupcake might expire if she takes too long, so she wants you to determine the fewest number of seconds it will take for her to travel from the top-left to the bottom-right of the grid.

Input

The first line of input contains an integer $$$t$$$ denoting the number of testcases. ($$$1 \leq t \leq 10^4$$$)

For each testcase, the first line will contain integers $$$n$$$ and $$$m$$$. ($$$1 \leq n, m \leq 10^3$$$)

The next $$$n$$$ lines will each describe a row of the grid. Each line will consist of a string of $$$m$$$ characters, where the $$$j$$$th character of the $$$i$$$th of these lines denotes the type of cell in the $$$i$$$th row and $$$j$$$th column of the grid. For each character in the string:

  • If this character is '.', then the corresponding cell is empty.
  • If this character is '>', then the corresponding cell contains a conveyor that is moving rightward.
  • If this character is 'v', then the corresponding cell contains a conveyor that is moving downward.
  • If this character is '<', then the corresponding cell contains a conveyor that is moving leftward.
  • If this character is '^', then the corresponding cell contains a conveyor that is moving upward.
  • If this character is '!', then the corresponding cell contains a switch.
  • If this character is '#', then the corresponding cell contains a wall.

It is guaranteed that the top-left and bottom-right cells in the grid are both empty. It is also guaranteed that there is a path from the top-left cell to the bottom-right cell.

Finally, it is guaranteed that the sum of $$$n \cdot m$$$ across all testcases is at most $$$10^6$$$.

Output

Output the fewest number of seconds it will take Sally to reach the bottom-right cell from the top-left cell.

Example
Input
3
4 5
.#...
.#.#.
.#.#.
...#.
4 5
.#...
!#^#v
.#^#v
...#.
7 7
.#.####
!#^....
v#^###v
v#..!#v
v#^###v
v#^###v
>>^###.
Output
26
22
43