글자 도장 (작은 입력)

문제

롤랜드는 고등학교 수학 교사다. 매일 학생들이 낸 답안지를 수백 장 받고, 답안지마다 'A', 'B', 'C' 중 하나를 성적으로 정한다. (롤랜드의 학생들은 똑똑해서 'D'나 'F'를 받는 일이 없다.) 성적을 다 정하면 롤랜드는 답안지를 조수인 당신에게 넘긴다. 당신이 할 일은 답안지마다 정해진 성적을 도장으로 찍는 것이다.

당신이 쓰는 도장은 단순하지만 잘 작동한다. 어떤 글자를 찍으려면 그 글자에 해당하는 판을 도장 앞면에 끼우고, 잉크를 묻힌 다음 종이에 누른다.

여기서 재미있는 점은 글자를 바꿀 때 판을 떼어내지 않아도 된다는 것이다. 기존 판 위에 새 판을 덧끼울 수 있다. 그래서 도장에 끼워진 판은 스택으로 볼 수 있고, 다음 세 연산을 지원한다.

푸시: 글자 하나를 스택 맨 위에 올린다. (새 판을 도장 앞면에 끼우는 것에 해당한다.)
팝: 스택 맨 위의 글자를 빼낸다. (앞면의 판을 떼어내는 것에 해당한다.)
출력: 스택 맨 위의 글자를 종이에 찍는다. (도장을 실제로 쓰는 것에 해당한다.) 이 연산을 하려면 스택에 글자가 하나 이상 있어야 한다.

'A', 'B', 'C'로 이루어진 문자열이 주어졌을 때, 이 문자열을 앞에서부터 순서대로 모두 찍는 데 필요한 최소 연산 횟수를 구한다. 스택은 비어 있는 상태에서 시작하고, 다 찍은 뒤에는 다시 비워야 한다. 판은 종류별로 얼마든지 있으므로 중간에는 몇 개든 써도 된다.

예를 들어 "ABCCBA"는 아래처럼 연산 12번으로 찍을 수 있다. 스택 칸은 맨 아래 글자부터 순서대로 적었다.

순서	연산	지금까지 찍은 문자열	스택
0	(시작)	(없음)	(없음)
1	A 푸시	(없음)	A
2	출력	A	A
3	B 푸시	A	AB
4	출력	AB	AB
5	C 푸시	AB	ABC
6	출력	ABC	ABC
7	출력	ABCC	ABC
8	팝	ABCC	AB
9	출력	ABCCB	AB
10	팝	ABCCB	A
11	출력	ABCCBA	A
12	팝	ABCCBA	(없음)

입력

첫 줄에 테스트 케이스의 개수 T가 주어진다. 이어지는 T개의 줄에 문자열 S가 한 줄에 하나씩 주어진다. S는 순서대로 찍어야 하는 글자들이다.

제한

S는 'A', 'B', 'C'로만 이루어진, 비어 있지 않은 문자열이다.
$1 \le T \le 100$
S의 길이는 100 이하다.

출력

각 테스트 케이스마다 "Case #x: N" 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, N은 S를 모두 찍는 데 필요한 최소 연산 횟수다.