You are taking a programming course which is graded using problem sets of different types. The course goes for a positive even number of days. You start the course with no problem sets. On each day of the course, you must do exactly one of the following:
All problem sets are different. There is no requirement on how many sets of each type must be submitted. Once you submit a set, you no longer have that set. Any problem sets that you have not submitted before the end of the course get you no points.
The problem sets are requested from and submitted to an artificially-intelligent teaching assistant. Strangely, the assistant has different moods — on each day it is in the mood for either "Coding" or "Jamming".
Thanks to some help from a senior colleague who understands the assistant very well, you know what sort of mood the assistant will be in on each day of the course. What is the maximum total score that you will be able to obtain?
The first line of the input gives the number of test cases, T; T
test cases follow. Each test case consists of one line with a string S
J characters. The i-th character of
S denotes the assistant's mood on the i-th day of the course. If it is
C, it is in the mood for "Coding"; if it is
J, it is
in the mood for "Jamming".
For each test case, output one line containing
Case #x: y, where
x is the test case number (starting from 1) and
the maximum number of points you can obtain for that case.
1 ≤ T ≤ 100.
The length of S is even.
2 ≤ the length of S ≤ 50.
2 ≤ the length of S ≤ 20000.
The sum of lengths of all S in the dataset is at most 150000.
5 CCJJ CJCJ CJJC CJJJ CCCCCC
Case #1: 20 Case #2: 10 Case #3: 20 Case #4: 15 Case #5: 30
This strategy is optimal for sample case #1:
Day 1: Request a "Coding" problem set (call it C1).
Day 2: Submit C1.
Day 3: Request a "Jamming" problem set (call it J1).
Day 4: Submit J1.
The following strategy is optimal for sample cases #2, #3, and #4: request C1, request J1, submit J1, submit C1.
For case #2, for example, note that you could not request C1, request J1, and then submit C1. Only the most recently requested problem set can be submitted.
In sample case #5, you can alternate between requesting a "Coding" problem set on one day, and submitting it on the next day.