러너 폰

러너 폰(Runner Pawns) 은 $8 \times 8$ 판 위에서 혼자 하는 체스 변형 게임이다. 체스와 마찬가지로 한 칸에는 한 번에 하나의 말만 놓을 수 있다. 말은 여러 개의 폰(러너 폰)과 하나의 말(나이트)로 이루어지며, 플레이어가 조종할 수 있는 것은 나이트뿐이다. 목표는 어떤 폰도 마지막 줄에 도달해 승진하기 전에 모든 폰을 잡는 것이다.

나이트는 'L' 모양으로 움직인다. 즉 항상 한 방향으로 두 칸, 그에 수직인 방향으로 한 칸 이동한다. 위 그림에서 H 는 나이트의 현재 위치를, • 는 한 번에 이동할 수 있는 칸을 나타낸다. 칸의 흑백 색은 구분하지 않는다.

칸에는 $1$ 부터 $64$ 까지 번호가 매겨져 있다.

01 02 03 04 05 06 07 08
09 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64

예를 들어 $22$ 번 칸에서 나이트는 $5$, $7$, $12$, $16$, $28$, $32$, $37$, $39$ 번으로 갈 수 있고, $57$ 번 칸에서는 $42$ 또는 $51$ 번으로만 갈 수 있다.

폰의 이동은 체스와 다르다. 각 폰은 대각선이 아니라 정확히 한 칸 아래로만 전진하며, 모든 폰이 동시에 움직인다. 폰은 판의 위쪽에서 아래쪽으로 내려가므로, $57$ 번부터 $64$ 번까지의 마지막 줄이 폰의 목표 지점이다.

한 라운드는 나이트의 이동 한 번과, 그 뒤 판에 남아 있는 모든 폰이 동시에 한 칸 전진하는 것으로 이루어진다.

• 나이트가 폰이 있는 칸으로 이동하면 그 폰을 잡는다. 잡힌 폰은 제거되며 전진하지 않는다.
• 폰이 마지막 줄에 도달하면 킹으로 승진한다. 그러면 나이트에게는 그 킹을 잡을 단 한 번의 이동만 주어진다. 잡지 못하면 킹이 달아나고 플레이어는 패배한다. 처음부터 마지막 줄에 있는 폰은 첫 라운드부터 이미 킹으로 취급한다.
• 나이트가 이동한 칸을, 그 라운드의 전진에서 살아남은 어떤 폰이 차지하게 된다면 나이트가 잡히고 플레이어는 패배한다.

모든 폰을 잡는 순간 플레이어는 승리한다. 주어진 초기 배치에 대해 나이트가 승리할 수 있는지, 가능하다면 필요한 나이트의 최소 이동 횟수를 구하는 프로그램을 작성하라.

입력은 여러 개의 인스턴스로 이루어지며, 각 인스턴스는 한 줄에 하나씩 주어진다. 각 줄은 폰의 개수 $P$ ($0 \le P \le 8$) 로 시작하고, 이어서 각 폰의 시작 칸을 나타내는 $P$ 개의 정수 $A_1, A_2, \ldots, A_P$ ($1 \le A_i \le 64$) 가 오며, 마지막으로 나이트의 시작 칸을 나타내는 정수 $H$ ($1 \le H \le 64$) 가 온다. 입력의 끝은 $P = 0$ 인 줄로 표시되며, 이 줄은 처리하지 않는다.

각 인스턴스에 대해 한 줄을 출력한다. 살아남은 킹이 달아나기 전에, 그리고 나이트 자신이 잡히지 않으면서 모든 폰을 잡을 수 있다면, 필요한 나이트의 최소 이동 횟수를 출력한다. 그렇지 않으면 impossible 을 출력한다.