[2018 SCPC 본선]

주사위

주사위의 전개도는 <그림 1>과 같다.

일반적인 주사위에서는 마주보는 두 면의 눈의 합은 항상 7이지만 본 문제에서는 주사위의 전개도에 대한 정보가 주어지기 때문에 그 성질이 만족되지 않을 수도 있다.

<그림 1>에서 보인 전개도에 대응하는 주사위를 입체적으로 나타내면 <그림 2>와 같다.

주사위가 평면에 어떻게 놓이는가에 따라 전면에서 본 값과 위에서 본 값이 다르다.

평면에 놓인 주사위를 전면에서 봤을 때 , 위에서 봤을 때 가 보인다면 “주사위는 자세 로 놓여있다”라고 말한다.

참고로, <그림 2>에서 보인 주사위는 자세 [1,3]으로 놓여있다.



평면에 격자가 있다. <그림 3>은 격자를 보여준다.

각 칸의 좌표는 그림에서 표시한 것과 같으며, 각 칸의 크기는 주사위 한 면의 크기와 같아서, 주사위가 어떤 칸에 놓이게 되면 그 칸은 완전히 덮이게 된다.

<그림 4>는 격자 (1,1) 자리에 자세 [1,3]으로 놓인 주사위의 상태를 보여준다.



어떤 격자 칸에 놓인 주사위를 이웃한 칸으로 이동할 때는 반드시 주사위를 해당 방향으로 굴려서 이동해야 한다. <그림 5>는 <그림 4>에서 보인 주사위를 우측으로 한 번 굴려 이동한 상황을 보여주고, <그림 6>은 <그림 4>에서 보인 주사위를 아래로 한 번 굴려 이동한 상황을 보여준다. 주사위는 격자 내에서 어떤 방향으로나 굴려 이동할 수 있지만 격자 밖으로는 나갈 수는 없다.

 

참고로, <그림 4>에서 보인 것처럼 (1,1) 자리에 자세 [1,3] 으로 놓인 주사위를 굴려서 (1,1) → (1,2) → (2,2) → (2,1) → (1,1)로 이동하면 자세가 [4,5]로 바뀌게 되고,
(1,1) → (2,1) → (2,2) → (1,2) → (1,1)로 이동하면 자세가 [2,6] 이 된다.



주사위 전개도에 대한 정보와 네 정수  가 주어질 때,

격자 (1,1)자리에 자세 로 놓인 주사위를 격자 내에서 이리저리 굴려 격자 자리에 자세 로 놓을 수 있는지를 판단하는 프로그램을 작성하고자 한다.

만약 그렇게 할 수 있다면 주사위를 최소 몇 번 굴려야 하는지 그 횟수를 보이고, 그렇지 않다면 –1을 출력하는 프로그램을 작성하라.

주사위의 전개도를 <그림 7>과 같이 표시할 때,  에 대응하는 값으로 주사위의 정보를 표시한다. 각 값은 1~6 사이의 정수이다.


입력

입력 파일에는 여러 테스트 케이스가 포함될 수 있다.

파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 가 주어지고,

이후 차례로   개의 테스트 케이스가 주어진다. ()

각 테스트케이스에 대해 , , , , , , , , , , ,   가 한 줄에 주어진다.



여기서, ~는 주사위 전개도 정보를 위한 수로서 1과 6사이의 서로 다른 정수이며,

은 격자의 줄 수, 은 격자의 칸 수를 나타내는 정수이고, ~는 주사위의 시작 자세와 마지막 자세를 나타내기 위한 정수이다.




출력

각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,

각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 는 테스트 케이스의 번호이다.



그 다음 줄에는 한 정수 값을 출력하되,

주어진 주사위에 대해, 격자 (1,1)자리에 자세 []로 놓인 것을 격자 내에서 이리저리 굴려 격자 ()자리에 자세 로 놓을 수 있다면

주사위를 최소 몇 번 굴려야 하는지 그 최소 횟수를 보이고, 격자 ()자리에 자세 로 놓는 것이 불가능하다면 –1을 출력하시오.

입출력예

입력
2
4 1 3 5 6 2 1 3 1 3 1 4
4 1 3 5 6 2 2 3 1 3 1 4
출력
Case #1
2
Case #2
-1

돌아가기