펼친 주사위

주사위는 던져졌다.

— 율리우스 카이사르 (기원전 100년 – 기원전 45년)

주사위는 아주 오랜 역사를 가진다. 주사위가 언제 어디에서 처음 생겨났는지는 분명하지 않다. 다만 기원전 3000년 이전부터 이집트에서 주사위를 사용했다는 사실은 알려져 있다.

그림 1: 주사위 사진

주사위를 평면에 나타낼 때에는 그림 2처럼 전개도로 표현하기도 한다. 아는 것처럼 같은 주사위를 나타내는 전개도는 여러 가지다. 하지만 이 문제에서는 그림 2와 같은 모양의 전개도만 생각한다. 편의를 위해 그림 3처럼 면에 번호를 붙인다.

그림 2: 주사위의 전개도

그림 3: 면의 번호

어느 날 M 박사는 주사위의 최적 전개도라는 개념을 도입했다. M-value가 최소인 전개도를 최적이라고 정의했다. M-value는 전개도에서 서로 인접한 면에 적힌 수들의 차의 합이다. 그림 2의 M-value는 |1 − 4| + |2 − 4| + |4 − 5| + |5 − 3| + |4 − 6| = 9이다. M 박사는 주사위에 대해 조금 잘못 알고 있어서 마주 보는 면에 적힌 수의 합이 항상 7인 것은 아니다. 그래도 각 면에는 1부터 6까지의 수가 하나씩 적혀 있고, 서로 다른 두 면에 같은 수가 적혀 있지는 않다.

연구 끝에 그는 여러 조건에서 최적 전개도를 찾아냈다. 그러나 안타깝게도 실수로 노트에 커피를 쏟아서 전개도의 일부를 읽을 수 없게 되었다.

여러분의 과제는 전개도의 일부만 보고 주사위의 전개도를 복원하는 프로그램을 작성하는 것이다.

그림 4: 예제 입력으로 주어진 전개도. 읽을 수 없는 면은 빈칸으로 표시했다.

첫째 줄에는 테스트 케이스의 수를 나타내는 양의 정수 T가 주어진다. 다음 T개 줄에 테스트 케이스가 주어진다.

각 테스트 케이스는 ‘1’부터 ‘6’까지의 숫자 또는 알파벳 소문자 ‘x’ 중 하나인 문자 여섯 개로 이루어진 한 줄이다. i번째 문자는 그림 3에서 번호 i인 면에 대응한다. 숫자는 그 면에 적힌 수를 나타내고, ‘x’는 수를 읽을 수 없어 프로그램이 결정해야 함을 나타낸다. 어떤 테스트 케이스에도 같은 숫자가 두 번 이상 나오지 않는다.

각 테스트 케이스마다, 입력에 주어진 면의 수는 그대로 두어야 한다는 조건에서 최적 전개도를 나타내는 숫자 여섯 개를 한 줄에 출력한다. i번째 숫자는 입력에서처럼 그림 3에서 번호 i인 면에 적힌 수를 나타내야 한다. 답이 여러 개라면 그중 아무거나 출력한다.