전쟁 게임

길동이는 요즘 컴퓨터 전략 게임에 빠져 있다. 이 게임에서 이기려면 먼저 상대 진형을 알아낸 다음, 거기에 맞는 병사로 자기 진형을 짜야 한다. 병사는 궁수, 창병, 기병 세 종류다. 궁수는 창병을 이기고, 창병은 기병을 이기고, 기병은 궁수를 이긴다. 상대 진형이 주어졌을 때 병사 수가 가장 적은 승리 진형을 구하는 프로그램을 작성하시오.

규칙은 다음과 같다.

1. 모든 병사는 정면만 공격하고 옆은 공격하지 못한다.
2. 그림처럼 길동이의 병사는 오른쪽에서 왼쪽으로, 상대의 병사는 왼쪽에서 오른쪽으로 움직인다.
3. 길동이의 병사가 같은 종류의 상대 병사와 맞붙으면 길동이의 병사가 진다. 길동이의 병사는 훈련이 덜 되어 있기 때문이다.
4. 한 번 맞붙으면 진 병사만 쓰러진다. 이긴 병사는 자리를 지키고 상대의 다음 병사와 곧바로 다시 맞붙는다.
5. 상대 병사가 모두 쓰러지면 길동이가 이긴다.

입력은 표준 입력으로 받는다. 첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 15$)가 주어진다. 이어지는 $T$개의 줄에는 상대 진형이 A, B, C로만 이루어진 문자열로 한 줄에 하나씩 주어진다. A는 궁수, B는 창병, C는 기병을 뜻한다. 각 문자열의 길이는 80을 넘지 않는다. 주어진 진형의 마지막 병사가 길동이 진형의 첫 병사와 가장 먼저 맞붙는다는 점에 주의하시오.

출력은 표준 출력으로 한다. 각 테스트 케이스마다 길이가 가장 짧은 승리 진형을 한 줄에 출력한다. 진형은 가장 먼저 싸우는 병사부터 차례대로 적는다. 길이가 가장 짧은 승리 진형은 언제나 하나뿐이다.