미니 빙고

Albert는 아래와 같은 3x3 격자판에서 하는 미니 빙고를 (mini BINGO) 즐겨한다. 이 문제를 풀기 위해 BINGO가 무슨 게임인지 알 필요는 없다.

Albert가 고안한 "미니 빙고" 놀이는 위와 같이 3x3 격자판에 서로 다른 영대문자 알파벳 9개를 적는 것으로 시작한다. 그리고 이 9개의 알파벳을 임의로 섞어서 길이 9인 문자열 $S$를 하나 고르는데 이를 seed (시드) 문자열이라 부른다.

시드 문자열 S에 등장하는 알파벳 순서대로 격자판의 칸을 색칠하는데, 아래 조건에 따라 해당 칸의 점수를 매긴다.

• 방금 색칠한 칸이 속한 열 위에 놓인 3개의 칸 모두가 색칠됐다면 1점을 추가한다.
• 방금 색칠한 칸이 속한 행 위에 놓인 3개의 칸 모두가 색칠됐다면 1점을 추가한다.
• 방금 색칠한 칸이 주-대각선 (위 예제에서 A, F, K) 위에 있고 주-대각선 위의 3칸 모두 색칠 됐다면 1점을 추가한다.
• 방금 색칠한 칸이 반-대각선 (위 예제에서 C, F, I) 위에 있고 반-대각선 위의 3칸 모두 색칠 됐다면 1점을 추가한다.

이 방법을 통해 얻은 각 칸의 점수는 언제나 0이상 4이하이며, 이를 시드문자열과 같은 순서대로 적어 길이가 9인 문자열을 얻을 수 있다 - 이렇게 얻은 점수 문자열을 $T(S)$라 하자.

예를 들어 시드 문자열 $S$ = "JGFACKIEB" 인 경우를 살펴보자. 아래 그림에서 상단 1열부터 5열까지, 그리고 하단 1열부터 4열까지의 격자판은 시드 문자열에 따라 알맞은 칸을 순서대로 칠한 모습을 보여준다.

• 처음으로 칠해지는 다섯 개의 칸은 "J", "G", "F", "A", "C"이며 각각 0점씩 점수를 부여한다.
• 여섯 번째로 "K"를 칠한 후 주-대각선과 3열 때문에 2점의 점수를 부여한다.
• 일곱 번째로 "I"를 칠한 후 3행과 반-대각선 때문에 2점의 점수를 부여한다.
• 여덟 번째로 "E"를 칠한 후 1열과 2행 때문에 2점의 점수를 부여한다.
• 마지막으로 "B"를 칠한 후 1행과 2열 때문에 2점의 점수를 부여한다.
• 이리하여 최종적으로 얻게 되는 점수 문자열은 $T(S)$ = "000002222"가 된다.

같은 격자판에서 시드 문자열이 $S$ = "ABEGKCFIJ" 일 때, 아래와 같은 순서로 격자를 칠하고, 이때의 점수 문자열은 "000002222"가 된다.

위 예제에서 보이듯 서로 다른 시드 문자열의 점수 문자열이 같을 수 있다.

Albert는 임의의 격자판과 임의의 시드 문자열 $S$가 있을 때 $T(S)$ 를 구하는 것이 너무 쉽다고 생각한다. 따라서 $S$의 점수 문자열을 구한 후, $S$와 같은 점수 문자열을 ($T(S)$) 만들어내는 모든 시드 문자열 중 사전순으로 가장 앞서는 시드 문자열을 찾고 싶다. Albert를 도와주자.

입력 첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 길이 9인 시드 문자열 $S$가 주어진다. 다음 세 줄에 걸쳐 3x3 격자판의 상태가 주어지는데 각 줄에 3개의 문자가 공백 없이 주어진다.

각 테스트 케이스의 정답인 $T(S)$와 해당 점수 문자열을 얻게 하는 시드 문자열 중 사전순으로 가장 앞서는 문자열을 공백으로 구분하여 각 줄에 출력한다.

• $1 \le T \le 100$
• 시드문자열 $S$는 길이가 9이며 알파벳인 'A'-'Z' 만을 포함한다. $S$에 중복된 알파벳은 입력으로 주어지지 않는다.
• 게임 격자판의 상태를 나타내는 총 9개의 알파벳은 시드 문자열 $S$에 포함된 알파벳만 주어지며, 중복된 알파벳은 입력으로 주어지지 않는다.

문자열의 사전순 정의: 길이가 $K$인 서로 다른 두 문자열 $A$와 $B$가 있을 때, 이 두 문자열이 처음 달라지는 위치가 $i$번째라 하고 이 위치의 문자를 각각 $A\[i]$, $B\[i]$라 했을 때, $A$와 $B$의 사전식 순서는 두 알파벳 $A\[i]$, $B\[i]$의 사전식 순서를 따른다.