성적 도장

Roland는 고등학교 수학 교사이다. 그는 매일 학생들에게서 수백 장의 시험지를 받는다. 각 시험지에 대해 그는 'A', 'B', 'C' 중 하나의 문자 성적을 신중하게 정한다. (Roland의 학생들은 너무 똑똑해서 'D'나 'F'처럼 더 낮은 성적을 받지 않는다.) 모든 성적을 정하고 나면 Roland는 조교인 당신에게 시험지를 넘긴다. 당신이 할 일은 각 시험지에 올바른 성적을 도장으로 찍는 것이다.

이를 위해 단순하지만 제대로 작동하는 문자 도장을 사용한다. 문자를 찍으려면 해당 문자에 대응하는 특수 판을 도장 앞면에 부착하고 잉크를 묻힌 다음 시험지에 찍는다.

흥미로운 점은 문자를 바꾸고 싶을 때 판을 제거하는 대신 기존 판 위에 새 판을 올리기만 해도 된다는 것이다. 실제로 문자 도장의 판들을 다음 연산을 지원하는 스택으로 생각할 수 있다.

• 스택의 맨 위에 문자를 푸시한다. (이는 도장 앞면에 새 판을 부착하는 것에 해당한다.)

• 스택의 맨 위에서 문자를 팝한다. (이는 도장 앞면에서 판을 제거하는 것에 해당한다.)

• 스택의 맨 위에 있는 문자를 출력한다. (이는 실제로 도장을 사용하는 것에 해당한다.) 물론 이 연산을 수행하려면 스택에 실제로 문자가 있어야 한다.

문자 성적('A', 'B', 'C')의 수열이 주어질 때, 전체 수열을 순서대로 출력하려면 몇 번의 연산이 필요한가? 스택은 빈 상태로 시작하며, 작업을 마쳤을 때 스택을 비워야 한다. 단, 그동안 사용할 수 있는 각 종류의 판은 무제한으로 주어진다.

예를 들어 수열 "ABCCBA"을 출력하려 한다면 아래와 같이 12번의 연산으로 출력할 수 있다.

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1GB. S는 'A', 'B', 'C'만 포함하는 비어 있지 않은 문자열이다.

작은 데이터 세트(테스트 세트 1 - 공개)

1 ≤ T ≤ 100. S의 문자 수는 최대 100개이다.

큰 데이터 세트(테스트 세트 2 - 비공개)

1 ≤ T ≤ 20. S의 문자 수는 최대 7000개이다.

입력 파일의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 순서대로 출력하려는 문자 수열을 나타내는 문자열 S 하나가 주어진다.

각 테스트 케이스마다 "Case #x: N"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작)이고, N은 S를 출력하는 데 필요한 스택 연산 횟수의 최솟값이다.