程序设计能力实训

1149. 字符串消除

单点时限: 2.0 sec

内存限制: 256 MB

给定一个由大写字母ABC构成的字符串s,按如下进行消除过程:

1、字符串s中连续相同字母组成的子串,如果子串的长度大于1,那么这些子串会被同时消除,余下的字符拼成新的字符串。

例如:ABCCBCCCAACC,CCCAA会被同时消除,余下ABB拼成新的字符串ABB

2、反复进行上述消除,直到新的字符串中相邻字符都不相同为止。

例如:ABCCBCCCAA经过一轮消除得到ABB,再经过一轮消除得到A

假设在对字符串s消除开始前,允许在s中任意位置(第一个字符之前、最后一个字符之后以及相邻两个字符之间)插入任意一个字符(A,B或者C),得到字符串t,然后对字符串t经过一系列消除。

请问该如何插入字符,使得字符串t中被消除掉的字符总数(包括插入的字符)最多?

输入格式

第 $1$ 行:整数 $T$ ($1 \le T \le 10$) 为问题数。

第 $2$ ~ $T+1$ 行:每个问题占一行,每行输入一个由ABC组成的字符串s,长度不超过100。

输出格式

对每个测试数据,首先输出一行问题的编号($0$ 开始编号,格式:case #0: 等)。在接下来一行中输出被消除掉的最大字符数。

样例

Input
3
ABCBCCCAA
AAA
ABC
Output
case #0:
9
case #1:
4
case #2:
2

提示

第一组数据:在ABCBCCCAA的第2个字符后插入C得到ABCCBCCCAA,消除后得到A,总共消除9个字符(包括插入的’C’)。

第二组数据:AAA插入A得到AAAA,消除后得到”“,总共消除4个字符。

第三组数据:无论是插入字符后得到AABC,ABBC还是ABCC都最多消除2个字符。

不限期开放

题目列表