Traffic Jam

Traffic jams are the nightmare of every driver. Nobody enjoys being stuck on crowded streets where cars crawl forward, if they move at all. Professional drivers face traffic jams often, and truck drivers are no exception. Can you help drivers find a way out of a traffic jam?

We model a small but tricky traffic jam on a $6 \times 6$ grid of squares. Vehicles (cars and trucks) sit on the grid at integer positions, as shown below. Every vehicle is 1 square wide. Cars are 2 squares long, and trucks are 3 squares long. Each vehicle is oriented either horizontally (East-West) or vertically (North-South).

Vehicles cannot pass through one another, cannot turn, and cannot move past the edge of the grid. A vehicle may slide only along its own orientation (a horizontally oriented vehicle moves only East-West, a vertically oriented one only North-South), as long as it is not blocked by another vehicle or by the edge. In a single move, exactly one vehicle slides; it may advance by as many squares as there is empty space in front of it. A slide of any length counts as one move.

The goal is to slide vehicles back and forth until one particular horizontally oriented vehicle (your own car, the black one in the picture above) drives off the rightmost (eastern) edge of the grid, where it is considered to have escaped the traffic jam. Write a program that finds a solution using the minimum possible number of moves.

The input consists of one or more scenarios. Each scenario begins with a single integer $n$ ($1 \le n \le 10$), the number of vehicles. Then follow 6 lines of 6 characters each. Each character is either a dot (.) for an empty square or a lowercase letter naming a vehicle. Your own vehicle is always horizontal and is written with the letter x. The other vehicles use letters assigned sequentially starting from a.

The last scenario is followed by a line containing a single zero.

For each scenario, print a single line Scenario #K requires X moves., where K is the scenario number (starting from 1) and X is the minimum number of moves needed for your car to escape the traffic jam.

If escaping is impossible, print You are trapped in scenario #K. instead.