<그림 1>과 같이 정사각형 \(N \times N\) 크기의 주차장이 있다. 이 주차장에는 차들이 많이 있는데, 우리 차를 주차장 밖으로 빼내어야 한다. 그런데 차를 움직일 수 있는 주차 관리원은 한 명 뿐이다. 이 주차 관리원이 하나의 차를 타고 그 차를 움직이는 것을 하나의 '작업'이라 부르기로 한다. 하나의 작업에 차는 앞뒤로 다른 차와 겹치지 않는 한 얼마든지 움직일 수 있다. 다음의 가정 하에 작업의 횟수를 가장 적게하면서 우리 차를 주차장 밖으로 빼내기 위해서 움직어야 하는 모든 차들의 순서를 계산하는 프로그램을 작성하시오.

<가정>

1. 모든 차의 폭은 1이고, 길이는 2 또는 3 이다.
2. 차는 주차되어 있는 방향에 따라 수직차 (예 : <그림 1>의 4번차), 수평차 (예 : <그림 1>의 3번차)로 구분한다. 수직차는 상하로만, 수평차는 좌우로만 움직일 수 있고 회전은 할 수 없다.
3. 같은 차에 대해서 여러 번 작업할 수 있다.
4. 우리 차 외에 다른 차는 작업 도중 조금이라도 주차장 밖으로 나갈 수 없으며, 우리 차가 완전히 주차장을 나가는 순간에 전체 작업은 끝난다 (<그림2>).
5. 우리 차가 수평차라면 오른쪽으로만 주차장을 나갈 수 있고, 수직차이면 위쪽으로만 나갈 수 있다.
6. 우리 차가 주차장을 빠져나갈 수 없는 경우도 있을 수 있다.

<평가 방법>

1. 각 테스트 데이터마다 실행 시간이 20초가 넘는 경우는 0점이다
2. 우리 차 이외에 다른 차가 작업 도중 주차장을 조금이라도 벗어나거나 작업 도중 차들이 서로 겹치는 경우가 발생하면 0점이다.
3. 1과 2의 경우가 아니라면 여러분들이 구한 작업 횟수에 따라 부준 점수가 주어질 수 있다.