육각 퍼즐

육각형 모양의 보드에는 바깥쪽 칸 6개와 가운데 칸 1개가 있다. 바깥쪽 칸은 입력에 쓰이는 순서대로 A, B, C, D, E, F라 부른다. 처음에는 가운데 칸이 비어 있고, 바깥쪽 칸에는 A부터 F까지의 동전이 하나씩 놓여 있다.

한 번의 이동에서는 빈 칸과 연결된 칸에 있는 동전 하나를 빈 칸으로 옮긴다. 칸의 연결은 다음과 같다.

• 바깥쪽 둘레: A-B, B-C, C-D, D-E, E-F, F-A
• 가운데 칸: B, E와 연결

목표 상태는 바깥쪽 칸 A부터 F까지에 각각 A, B, C, D, E, F 동전이 놓이고 가운데 칸이 비어 있는 상태다.

초기 상태가 주어졌을 때, 목표 상태로 만드는 최소 이동 횟수와 그때 움직인 동전들의 순서를 구하라. 어떤 방법으로도 목표 상태를 만들 수 없으면 불가능하다고 판단한다.

첫째 줄에 테스트 케이스의 개수 T (1 <= T <= 1000)가 주어진다. 다음 T개의 줄에는 초기 상태를 나타내는 길이 6의 문자열이 주어진다. 이 문자열은 A부터 F까지의 순열이며, 바깥쪽 칸 A부터 F까지에 놓인 동전을 차례대로 나타낸다. 가운데 칸은 처음에 비어 있다.

각 테스트 케이스마다 한 줄을 출력한다. 퍼즐을 풀 수 있으면 최소 이동 횟수, 공백 하나, 움직인 동전의 라벨을 순서대로 출력한다. 이동 횟수가 0이면 이 문자열은 비어 있을 수 있다. 퍼즐을 풀 수 없으면 -1을 출력한다.