Earthstone Keeper is a famous roguelike game created by *Lizard Entertainment*. In this game, an adventurer will explore in a single layer dungeon of `N` × `M` size.

The adventurer starts at the room `(SR, SC)` and he wants to go to the room located at `(TR, TC)` since there hides a big treasure box full of gold and diamonds! However, exploration is not always an easy job. There are many traps and monsters in the dungeon. To be specific, there are 4 types of rooms:

- Common. The room is safe.
- Obstacles. The room is full of obstacles that the adventurer cannot enter it.
- Trap. The room has been set up with a trap. The trap will be triggered when the adventurer enters the room. When the adventurer leaves, the trap will reset so it can be triggered next time.
- Monster. There is a monster standing in it. If the adventurer walks into a monster room or any room adjacent to a monster room, the monster will immediately rush up to the adventurer and fight with him. Once the monster is killed, the adventurer can continue his exploration. Of course, the monster will not revive.

Two rooms are adjacent if and only if they share an edge. The adventurer can take 1 minute to go from a room to an adjacent room. Traps or monsters are always dangerous. More precisely, there is a fatality value for each trap and monster. Although our adventurer is strong and swift, battling with a deadly monster or dodging a rolling stone trap are not wise options.

The dungeon has been sealed by its owner with a powerful magic so the adventurer can not escape to outside until he found the treasure. By the way, being afraid of monsters battling with each other, the dungeon owner will not set any two monster rooms adjacent to each other. The room `(SR, SC)` and `(TR, TC)` are always common rooms and will not be adjacent to any monster room.

The adventurer want choose a best path to the treasure. The total fatality value of all monsters he killed and all traps he triggered should be as low as possible (If a trap was triggered multiple times, the fatality should also count multiple times). Among all safest paths, he want to choose the shortest path lead to the treasure room.

Please write program to help the adventurer find out the best path to the treasure.

There are multiple test cases. The first line of input contains an integer `T` indicating the number of test cases. For each test case:

The first line contains two integers `N` and `M` (1 <= `N`, `M` <= 500). The second line contains 4 integers `SR`, `SC`, `TR`, `TC` (1 <= `SR`, `TR` <= `N` and 1 <= `SC`, `TC` <= `M`).

For the next `N` lines, each line contains `M` characters indicating the map of dungeon. Each type of room is marked as:

- Common: "."
- Obstacles: "#"
- Trap: from "a" to "z"
- Monster: from "A" to "Z"

The fatality value of trap "a" and monster "A" is 1. The fatality value of trap "b" and monster "B" is 2, and so on. Therefore, the most dangerous trap "z" or monster "Z" has its fatality value equal to 26.

提交代码