글자 도장 (큰 입력)

문제

롤랑은 고등학교 수학 교사다. 매일 학생에게서 답안지를 수백 장 받고, 답안지마다 '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$ 는 순서대로 찍어야 하는 글자를 이어 놓은 것이다.

제한

$1 \le T \le 20$
$S$ 는 'A', 'B', 'C'로만 이루어진 빈 문자열이 아닌 문자열이다.
$S$ 의 길이는 7000 이하다.

출력

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