Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB

So he invented the magic door which opens with a magic spell and automatically closes after a while.

He put the doors in many places in his house, so it became very difficult to move around.

He wants to know the shortest time to move between two places in his house, so he cast a magic spell and summoned you, the excellent programmer.

KM's house consists of a matrix of square cells. A cell is one of the followings.

. empty # wall ^ start $ goal a-h magic circle A-H magic doorHe can move one cell to its

He can move into empty cells, start, goal, magic circles, and opened magic doors.

The house is surrounded by the walls, so he can't go out.

On a magic circle, he can cast a magic spell by consuming arbitrary amount of MP (Magic power). This takes a second. When he uses

He can move into a door which closes at that time.

There may be more than one same magic circles or same magic doors. In this case, all the corresponding magic doors opens when he cast a magic spell on any magic circles.

At the beginning, his MP is

Find the shortest time to move from the start to the goal.

Subsequent

Each character

`.`

, `#`

, `^`

, `$`

, `a`

-`h`

, `A`

-`H`

.There is only one start and one goal in the map.

If it is impossible to reach the goal, output

`-1`

instead.
1 3 ^.$

2

1 4 ^aA$

5

1 4 ^aB$

-1

3 3 ^AB a#A b#$

19