메트로 마닐라 우회로

메트로 마닐라에는 중심(마닐라)을 둘러싼 반원 모양의 순환도로 C1부터 C6까지 여섯 개와, 중심에서 바깥으로 뻗어 나가는 방사도로 R1부터 R10까지 열 개가 있다. R1이 가장 남쪽, R10이 가장 북쪽이고 번호는 반원을 따라 이 순서대로 붙는다. C6은 아직 건설 중이지만 이 문제에서는 통행할 수 있다고 가정한다.

교차점은 순환도로 Cc와 방사도로 Rr이 만나는 지점이고 (Cc, Rr)로 적는다. 중심은 (C0, R0)이다.

거리는 다음과 같이 센다.

• 방사도로에서 (Cc, Rr)과 (Cc+1, Rr)을 잇는 한 구간은 1이다. 중심과 (C1, Rr) 사이도 1이다. 예를 들어 (C1, R3)에서 (C2, R3)까지는 1이다.
• 순환도로 Cc에서 (Cc, Rr)과 (Cc, Rr+1)을 잇는 호 하나는 c이다. 예를 들어 (C3, R1)에서 (C3, R2)까지는 3이다.
• 순환도로가 반원이므로 R1과 R10은 양쪽 끝이고, 이 둘을 직접 잇는 호는 없다.

번호판 끝자리로 통행을 제한하는 제도(number coding scheme) 때문에 차량은 번호판 끝자리와 번호가 같은 방사도로를 달릴 수 없다. 번호판이 ABC-123인 차량은 끝자리가 3이라서 R3을 쓰지 못하고, 끝자리가 0인 차량은 R10을 쓰지 못한다. 끝자리마다 순환도로 하나도 함께 막히며, C6만 언제나 열려 있다.

금지되는 것은 막힌 도로를 따라 달리는 일뿐이다. 막힌 도로 위의 교차점에 서 있거나 그 도로를 가로질러 지나가는 것은 허용한다. 그래서 번호판이 ABC-123인 차량은 (C1, R2)에서 (C5, R1)까지 최단 거리가 5지만(그림의 굵은 선), 번호판이 CBA-321인 차량은 9다. 목적지에 아예 도달하지 못하는 차량도 있다.

출발점과 목적지, 번호판 끝자리가 주어질 때 출발점에서 목적지까지 최단 거리를 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 공백으로 구분된 한 자리 수 다섯 개 c1 r1 c2 r2 d다. (Cc1, Rr1)이 출발점, (Cc2, Rr2)가 목적지이고 d는 번호판 끝자리다. 방사도로 번호 0은 R10을 뜻한다. 순환도로 번호가 0이면 그 지점은 중심이고, 이때 방사도로 번호도 0이다. 테스트 케이스 사이에 빈 줄은 없으며, 마지막 테스트 케이스 다음 줄에는 0 하나만 있다.

각 테스트 케이스마다 Case x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고 y는 최단 거리다. 목적지에 도달할 수 없으면 대신 Case x: not possible을 출력한다.