Impasse (+)

Time Limit: 5000 ms Memory Limit: 65536 KiB

Problem Description

 Impasse is a very interesting web game. In this game, you are in a 3*n maze and you should avoid obstacles and reach the destination.
You can move to four directions (north, south, east and west). And you should notice that the maze is connected between north and south, in other words you can go from (1, 1) to (3, 1) by only one step to north.

Then there are some different kinds of blocks in that maze:
‘o’: Immovable obstacle.
‘n’: It will move to a north position when you move north or south.
‘u’: It will move to a south position when you move north or south.
‘m’: It will move to a north position when you move east or west.
‘w’: It will move to a south position when you move east or west.
You can never stand on the positions described above. And for ‘-’, ‘=’ and ‘x’, you can step on it when it’s off. Details:
‘-’: It will change its status when you move north or south. (Default on)
‘=’: It will change its status when you move north or south. (Default off)
‘x’: You can’t stand on it when it is on. (All default on)
‘s’: All the 'x' status will change when you step on it. And this switch will disappear forever.
And then:
‘.’: Empty position.
‘+’: The position you start with. (Exactly one)
‘y’: Destination. (Exactly one)
All these blocks may stay in a same position, and they would not affect each other.
You should know that these blocks change as soon as you make a move. You just need to check the status after each step.

Input

First line is an integer t (t<=25), indicating the number of test cases.
For each case, there is an integer n (n<=100) first.
Then three lines, each line has n characters described the maze.

Output

For each case in the input, print one line: "Case X: Y", where X is the test case number (starting with 1) and Y is the minimal steps to solve it. If it is unsolvable, just output -1 instead.

Sample Input

2
4
.u.o
+uny
..no
10
.msx.moooo
+.w.-=ssxy
.mw.w.oooo

Sample Output

Case 1: 5
Case 2: 43

Hint

For the first case, you can solve it by “NESEE”, 5 steps.

Source

2012年"浪潮杯"山东省第三届ACM大学生程序设计竞赛