Tobo or not Tobo

토보(Tobo)는 1부터 9까지 번호가 매겨진 3×3 격자 모양의 플라스틱 판 위에서 하는 놀이로, 그림 (a)와 같이 생겼다. 판에는 A부터 D까지 이름 붙은 네 개의 다이얼이 있다. 각 다이얼은 시계 방향이나 반시계 방향으로 90° 돌릴 수 있으며, 다이얼을 돌리면 그것을 둘러싼 네 칸이 함께 회전한다. 예를 들어 그림 (b)는 다이얼 A를 시계 방향으로 한 번 돌린 뒤의 상태이고, 그림 (c)는 그림 (b)에서 다이얼 D를 반시계 방향으로 한 번 돌린 뒤의 상태이다.

네 다이얼은 격자 안쪽 모서리에 위치한다. 다이얼 A는 1, 2, 4, 5번 칸을, 다이얼 B는 2, 3, 5, 6번 칸을, 다이얼 C는 4, 5, 7, 8번 칸을, 다이얼 D는 5, 6, 8, 9번 칸을 둘러싼다. 90°를 한 번 돌리면 이 네 칸이 회전 방향으로 한 칸씩 순환 이동한다.

아이들은 토보로 서로 겨루기를 좋아한다. 그림 (a)의 배열(이를 표준 배열이라 하자)에서 시작해 한 아이가 다이얼을 무작위로 X번 돌려 판을 섞는다. 그러면 다른 아이가 X번 이하의 회전만으로 판을 표준 배열로 되돌리려 하며, 회전 횟수가 적을수록 좋다. 주어진 판을 표준 배열로 되돌리는 데 필요한 최소 회전 횟수를 구하라.

입력은 하나 이상의 테스트 케이스로 이루어지며, 각 케이스는 한 줄에 주어진다. 각 줄은 정확히 10개의 십진수 숫자로 이루어진다. 첫 번째 숫자를 Y라 하자. Y는 판을 섞을 때 돌린 횟수이자, 판을 되돌릴 때 사용할 수 있는 최대 회전 횟수이다. 나머지 9개의 숫자는 모두 0이 아니며, 현재 판의 배열을 행 우선(위에서 아래로, 왼쪽에서 오른쪽으로) 순서로 나타낸다.

입력의 끝은 0이 10개인 줄로 표시되며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다 다음 형식으로 한 줄을 출력한다.

k. R

여기서 k는 테스트 케이스 번호(1부터 시작), 마침표 뒤에는 공백 하나가 오고, R은 판을 표준 배열로 되돌리는 데 필요한 최소 회전 횟수이다. 최대 Y번의 회전으로 되돌릴 수 없다면 R 대신 -1을 출력한다.