교통 체증 탈출

교통 체증은 모든 운전자의 악몽입니다. 차들이 아주 느리게, 혹은 아예 움직이지 못하는 꽉 막힌 도로에 갇히는 것을 좋아하는 사람은 없습니다. 전문 운전자들도 교통 체증을 자주 겪으며, 트럭 운전자들도 예외는 아닙니다. 운전자들이 교통 체증에서 빠져나갈 길을 찾도록 도와줄 수 있나요?

작지만 까다로운 교통 체증을 $6 \times 6$ 격자 위에서 모형화합니다. 자동차와 트럭 같은 차량들이 아래 그림처럼 격자의 정수 위치에 놓여 있습니다. 모든 차량의 폭은 1칸입니다. 자동차는 길이가 2칸, 트럭은 길이가 3칸입니다. 각 차량은 가로(동서) 또는 세로(남북) 방향으로 놓여 있습니다.

차량은 서로를 통과할 수 없고, 방향을 바꿀 수 없으며, 격자 밖으로 나갈 수 없습니다. 각 차량은 자신이 놓인 방향으로만 움직일 수 있습니다(가로 차량은 동서로만, 세로 차량은 남북으로만). 다른 차량이나 격자의 가장자리에 막히지 않는 한 이동할 수 있습니다. 한 번의 이동에서는 정확히 한 대의 차량만 움직이며, 앞에 빈 공간이 있는 만큼 여러 칸을 한꺼번에 나아갈 수 있습니다. 몇 칸을 움직이든 한 번의 이동은 1회로 셉니다.

목표는 차량들을 앞뒤로 움직여, 가로로 놓인 특정 차량(위 그림에서 검은색으로 표시된 여러분의 자동차)이 격자의 가장 오른쪽(동쪽) 가장자리로 빠져나가게 하는 것입니다. 그 차량이 오른쪽 가장자리를 벗어나면 교통 체증에서 탈출한 것으로 봅니다. 가능한 최소 이동 횟수로 탈출하는 방법을 찾는 프로그램을 작성하세요.

입력은 하나 이상의 시나리오로 이루어집니다. 각 시나리오는 차량의 수를 나타내는 정수 $n$ ($1 \le n \le 10$)으로 시작합니다. 이어서 각각 6개의 문자로 이루어진 6개의 줄이 주어집니다. 각 문자는 빈 칸을 나타내는 점(.)이거나 차량을 나타내는 소문자입니다. 여러분의 차량은 항상 가로로 놓여 있으며 문자 x로 표시됩니다. 나머지 차량은 a부터 순서대로 알파벳을 사용합니다.

마지막 시나리오 뒤에는 0 하나만 있는 줄이 옵니다.

각 시나리오마다 한 줄에 Scenario #K requires X moves.를 출력합니다. 여기서 K는 시나리오 번호(1부터 시작)이고 X는 여러분의 자동차가 교통 체증에서 탈출하는 데 필요한 최소 이동 횟수입니다.

탈출이 불가능하면 대신 You are trapped in scenario #K.를 출력합니다.