Letter Stamper (Small)

Problem

Roland teaches high-school math. Every day he collects hundreds of papers from his students, and for each paper he picks one letter grade: 'A', 'B', or 'C'. (Roland's students are too smart to get a 'D' or an 'F'.) Once the grades are decided, Roland hands the papers to his assistant, you. Your job is to stamp the right grade onto each paper.

The stamp you use is low-tech but it works. To print a letter, you attach the plate for that letter to the front of the stamp, dip it in ink, and press it onto the paper.

The useful part is that you do not have to remove a plate to switch letters. You can attach a new plate on top of the old one. The plates on the stamp therefore behave like a stack with these three operations.

Push: put a letter on top of the stack. (You attach a new plate to the front of the stamp.)
Pop: remove the letter on top of the stack. (You take the front plate off.)
Print: stamp the letter on top of the stack onto the paper. (You actually use the stamp.) The stack must hold at least one letter for this operation.

Given a string of 'A', 'B', and 'C', find the minimum number of operations needed to print the whole string in order. The stack starts empty and must be empty again when you are done. You have an unlimited supply of plates of each kind, so you may use as many as you like in between.

For example, "ABCCBA" can be printed in 12 operations as shown below. The stack column lists the letters from the bottom up.

Step	Operation	Printed so far	Stack
0	(start)	(none)	(none)
1	Push A	(none)	A
2	Print	A	A
3	Push B	A	AB
4	Print	AB	AB
5	Push C	AB	ABC
6	Print	ABC	ABC
7	Print	ABCC	ABC
8	Pop	ABCC	AB
9	Print	ABCCB	AB
10	Pop	ABCCB	A
11	Print	ABCCBA	A
12	Pop	ABCCBA	(none)

Input

The first line contains the number of test cases, T. Each of the next T lines contains one string S, the letters you have to print in order.

Limits

S is a non-empty string containing only the letters 'A', 'B', and 'C'.
$1 \le T \le 100$
S has at most 100 characters.

Output

For each test case, print one line in the form "Case #x: N", where x is the test case number starting from 1 and N is the minimum number of stack operations needed to print S.