【状压DP】
题目翻译

在遥远的木星卫星上，一些开发者大会活动即将举行！
它们称为IO（大写I，大写O）、Io（大写I，小写o）、iO（小写i，大写O）和IO（小写i，小写o）。

宣传活动的最佳方式是使用专用计算机，每次打印一个字符的活动名称，输出显示在数字显示器上。每台这样的计算机只知道一个事件的名称，并被编程为打印其事件的名称零次或多次。

例如，一台被编程为打印IO两次的计算机打印一个I，然后是一个O，然后是一个I，然后是一个O，最后形成一个IO字符串。

会议组织者正使用一台计算机为每个活动做广告。每个打印机可以打印其事件名称零次或多次。

此外，计算机不一定都被编程成打印相同的次数。

计算机都已完成打印，但不幸的是，它们都打印到同一个显示器上！
因为计算机是并发打印的，所以最终输出字符串中的事件名可能是交错的。
您正在考虑可能的交错方式。

例如string IiOioIoO 可能是这样形成的:
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

在这种情况下，Io事件被打印了两次，iO事件被打印了两次，另外两个事件根本没有打印。

请注意，不能解释成IO打印了两次。在这种情况下，剩余的输出iioo必须来自io计算机，
但这是不可能的-计算机必须连续打印i两次，这是不允许的。

但是，IO可能被打印了一次：
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

给定最终的输出字符串，事件IO被打印的最大可能次数是多少？
保证字符串至少有一个有效的解释。例如， oI, IOI, 和 IIOO 不是有效的输入。

Problem
You do not need to read the Interleaved Output: Part 1 problem to be able to solve this problem. Both Part 1 and Part 2 have the same first two paragraphs (not including this informational text). We have underlined the critical difference between the two parts.

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 by using special computers that print the event’s name one character at a time, with the output appearing on a digital display. Each such computer only knows the name of one event, and is programmed to print its event’s name zero or more times. For example, a computer programmed to print IO twice prints an I, followed by an O, followed by an I, followed by an O, for a final string of IOIO.

You know that the conference organizers are using exactly one computer to advertise each event. Each printer may print its event name zero or more times. Moreover, 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.

Notice that 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 have come from the io computer, but that is impossible — that computer would have had to have printed i twice in a row, which is not allowed.

However, it is possible that the IO computer 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?

It is guaranteed that the string has at least one valid interpretation. For example, oI, IOI, and IIOO are not valid inputs.

Input
The first line of the input gives the number of test cases, T. T lines follow; each represents a single test case. Each case consists of a string S containing only the characters from the set I, O, i, and o.

Output
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.

Limits
Time limit: 20 seconds per test set.
Memory limit: 1GB.
1 ≤ T ≤ 100.
The length of S is even.
There is at least one interpretation of the string that is consistent with the rules above. (That is, there is some way to assign each character to one of the four computers, such that the substring corresponding to each computer consists of zero or more repeats of that computer’s event’s name.)

Test set 1 (Visible Verdict)
2 ≤ the length of S ≤ 8.

Test set 2 (Hidden Verdict)
2 ≤ the length of S ≤ 100.

Sample

Input

5
IiOioIoO
IIOiOo
IoiOiO
io
IiOIOIoO

Output

Case #1: 1
Case #2: 1
Case #3: 0
Case #4: 0
Case #5: 3

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

In Sample Case #2, it is not possible that IO was advertised twice, because then the IO computer would have had to print two Is in a row. However, it is possible that IO was advertised once, e.g.:
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 Sample Case #3, notice that it is not possible that IO was advertised. The second character, o, must have been printed by the same computer that printed the first character I.

In Sample Case #4, notice that it is possible that I and/or O might not even show up in the string.

In Sample Case #5, it is possible that IO was advertised as many as three times (and in that case, io was advertised once).

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=110;
char a[N];
int dp[N][16]; //N=第i个字符，16=每台机器开关的16种状态
//0000二进制从高位到低位分别表示：IO，Io，iO，io
//函数值为最大IO宣传次数

int main(){
    int T,casei=0;
    cin>>T;
    while(T--){
        memset(dp,-1,sizeof dp);
        casei++;
        cin>>a;
        int n=strlen(a);
        dp[0][0]=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<16;j++){
            if(dp[i][j]<0)continue;
            if(a[i]=='I' && !(j&(1<<3)))
                dp[i+1][j+(1<<3)]=max(dp[i+1][j+(1<<3)],dp[i][j]);
            if(a[i]=='I' && !(j&(1<<2)))
                dp[i+1][j+(1<<2)]=max(dp[i+1][j+(1<<2)],dp[i][j]);
            if(a[i]=='i' && !(j&(1<<1)))
                dp[i+1][j+(1<<1)]=max(dp[i+1][j+(1<<1)],dp[i][j]);
            if(a[i]=='i' && !(j&(1<<0)))
                dp[i+1][j+(1<<0)]=max(dp[i+1][j+(1<<0)],dp[i][j]);
            if(a[i]=='O' && (j&(1<<3)))
                dp[i+1][j-(1<<3)]=max(dp[i+1][j-(1<<3)],dp[i][j]+1);
            if(a[i]=='O' && (j&(1<<1)))
                dp[i+1][j-(1<<1)]=max(dp[i+1][j-(1<<1)],dp[i][j]);
            if(a[i]=='o' && (j&(1<<2)))
                dp[i+1][j-(1<<2)]=max(dp[i+1][j-(1<<2)],dp[i][j]);
            if(a[i]=='o' && (j&(1<<0)))
                dp[i+1][j-(1<<0)]=max(dp[i+1][j-(1<<0)],dp[i][j]);
            }

        }



        cout<<"Case #"<<casei<<": "<<dp[n][0]<<endl;


    }
    return 0;
}