提示: 欢迎访问OurACM平台。
Problem 1982 ABC

Accept: 109    Submit: 301
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Abcdxyzk is a naughty boy. One day he plays a game with his MM. There is one long long cake with N blocks. Every block has one color, say blue, red, yellow… here we use lower case letter to express the color, such that ‘a’ = red, ‘b’ = yellow, ‘c’ = blue. Now abcdxyzk and his MM only want to cut the long long cake into some pieces which exactly contains 3 blocks with color ‘abc’ or ‘bca’. Here abcdxyzk only cut ‘abc’ and his MM only cut ‘bca’. However, if abcdxyzk get A0 pieces of ‘abc’ and his MM get A1 pieces of ‘bca’ , then they will both eat min{ A0, A1} pieces of cakes. Because the cake is really delicious, so both abcdxyzk and his MM want to have more! Now could you tell abcdxyzk the maximum piece of cake he and his MM will have?

Input

In the first line there is an integer T, indicates the number of test cases. (T <= 100)

In each case, the first line contains only one string S indicate the cake. (1 <= |S| <= 1000). each block only has one letter ‘a’, ‘b’, or ‘c’.

Output

For each case, output “Case idx: “ first where idx is the index of the test case start from 1, then an integer indicate the maximum piece of cake he and his MM will have.

Sample Input

3 abcbca abcabc abcabcabcabca

Sample Output

Case 1: 1 Case 2: 0 Case 3: 2

Hint

In first case, [abc]{bca}, A0 = 1, A1 = 1, so the answer is 1.

Source

FOJ有奖月赛-2010年11月

Submit  Back  Status  Discuss