Interleaved Output: Part 2

You do not need to read Interleaved Output: Part 1 to solve this problem. Both parts share the same first two paragraphs (not counting this note), but they ask for different values.

On a distant moon of Jupiter, some developer conference events are about to happen. They are called IO (uppercase I, uppercase O), Io (uppercase I, lowercase o), iO (lowercase i, uppercase O), and io (lowercase i, lowercase o).

The best way to advertise an event is with special computers that print the event's name one character at a time, with the output appearing on a digital display. Each computer knows the name of only one event and is programmed to print that name zero or more times. For example, a computer programmed to print IO twice prints an I, then an O, then an I, then an O, for a final string of IOIO.

You know that the conference organizers use exactly one computer to advertise each event. Each computer may print its event name zero or more times. The computers are not necessarily all programmed to print the same number of times.

The computers have all finished printing, but unfortunately they all printed to the same display. Because the computers printed concurrently, event names in the final output string may be interleaved. You are considering the possible ways in which that string could have been produced.

For example, the string IiOioIoO could have been produced as follows:

    index:  1 2 3 4 5 6 7 8
    IO:     . . . . . . . .
    Io:     I . . . o I o .
    iO:     . i O i . . . O
    io:     . . . . . . . .
    string: I i O i o I o O

In this interpretation, the Io event was advertised twice, the iO event was advertised twice, and the other two events were not advertised at all.

There is no valid interpretation of this string in which the IO computer advertised its event twice. In that case the remaining output, iioo, would have had to come from the io computer, which is impossible because that computer would have had to print i twice in a row.

However, the IO computer could have advertised its event once, as in the following interpretation:

    index:  1 2 3 4 5 6 7 8
    IO:     . . . . . I . O
    Io:     I . . . o . . .
    iO:     . i O . . . . .
    io:     . . . i . . o .
    string: I i O i o I o O

Given a final output string, what is the maximum possible number of times that the event IO could have been advertised?

The string is guaranteed to have at least one valid interpretation. For example, oI, IOI, and IIOO are not valid inputs.

The first line of the input gives the number of test cases, T. T lines follow, each holding a single test case. Each test case is a string S consisting only of the characters I, O, i, and o.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the maximum number of times IO could have been advertised, as described above.

• $1 \le T \le 100$
• The length of S is even.
• The string has at least one interpretation consistent with the rules above. (That is, there is some way to assign each character to one of the four computers so that the subsequence assigned to each computer consists of zero or more repeats of that computer's event name.)

Case #1 of the sample is the one described in the statement. (If you have read Interleaved Output: Part 1, notice that it is the same input as the first sample case of that problem, but the output is different.)

In Case #2, IO cannot have been advertised twice, because the IO computer would then have had to print two Is in a row. However, IO could have been advertised once, for example:

    index:  1 2 3 4 5 6
    IO:     I . O . . .
    Io:     . I . . . o
    iO:     . . . i O .
    io:     . . . . . .
    string: I I O i O o

In Case #3, IO cannot have been advertised at all. The second character, o, must have been printed by the same computer that printed the first character, I.

Case #4 shows that I, O, or both might not appear in the string at all.

In Case #5, IO could have been advertised as many as three times (and in that case, io was advertised once).