2×2×2 큐브 맞추기

학생들이 큐브에 빠져 수업을 듣지 않자, 한 교수는 큐브를 대신 풀어 주는 프로그램이 있으면 학생들이 흥미를 잃을 것이라고 생각했다. 교수가 큐브의 크기는 정해 주지 않았으므로 여기서는 2×2×2 큐브만 다룬다.

2×2×2 큐브는 코너 조각 8개로만 이루어진다. 각 면은 2×2 칸으로 나뉘고, 완성된 큐브는 여섯 면이 각각 한 가지 색이다. 이 큐브에는 고정된 중심 조각이 없으므로 어떤 색이 어느 면에 오는지는 상관없다. 여섯 면이 각각 한 색이기만 하면 완성이다.

한 번의 회전은 큐브의 한 면을 시계 방향이나 반시계 방향으로 90도 돌리는 것이다. 180도 회전은 회전 두 번으로 센다.

섞인 큐브의 상태가 주어지면 그 큐브를 완성하는 데 필요한 최소 회전 수를 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 100$).

각 테스트 케이스는 큐브의 전개도를 나타내는 여섯 줄이고, 테스트 케이스 사이에는 빈 줄이 하나씩 있다. 전개도의 모양은 다음과 같다.

UU
UU
LL FF RR BB
LL FF RR BB
DD
DD

처음 두 줄은 윗면이다. 가운데 두 줄은 왼쪽 면, 앞면, 오른쪽 면, 뒷면을 이 순서로 왼쪽부터 적고 공백 하나로 구분한 것이다. 마지막 두 줄은 아랫면이다.

각 면은 바깥에서 그 면을 정면으로 본 모습을 적는다. 왼쪽 면, 앞면, 오른쪽 면, 뒷면은 큐브의 옆면을 한 바퀴 도는 순서이고, 네 면 모두 첫 줄이 윗면과 맞닿는다. 윗면은 앞면 위쪽으로 펼친 모습이라서 첫 줄이 뒷면과, 둘째 줄이 앞면과 맞닿는다. 아랫면은 앞면 아래쪽으로 펼친 모습이라서 첫 줄이 앞면과, 둘째 줄이 뒷면과 맞닿는다. 윗면과 아랫면 모두 왼쪽 열이 왼쪽 면과 맞닿는다.

색은 G, R, O, B, Y, W 여섯 글자로 적는다. 입력으로 주어지는 큐브는 모두 여섯 색이 서로 다른 완성된 큐브를 섞어서 만든 것이다. 따라서 각 색은 정확히 네 번씩 나오고, 위에서 설명한 회전만으로 반드시 완성할 수 있다.

각 테스트 케이스마다 큐브를 완성하는 데 필요한 최소 회전 수를 한 줄에 하나씩 출력한다.