뒤섞인 출력: Part 2

문제

이 문제를 풀기 위해 Interleaved Output: Part 1을 읽을 필요는 없다. 두 문제는 이 안내문을 뺀 첫 두 문단이 같고, 구하는 값이 다르다.

목성의 머나먼 위성에서 곧 개발자 컨퍼런스 행사가 열린다. 행사 이름은 IO(대문자 I, 대문자 O), Io(대문자 I, 소문자 o), iO(소문자 i, 대문자 O), io(소문자 i, 소문자 o)이다.

행사를 홍보하는 가장 좋은 방법은 특수한 컴퓨터를 쓰는 것이다. 이 컴퓨터는 행사 이름을 한 글자씩 출력하고, 출력한 글자는 디지털 전광판에 나타난다. 컴퓨터마다 행사 하나의 이름만 알고 있으며, 그 이름을 0번 이상 출력하도록 프로그래밍되어 있다. 예를 들어 IO를 두 번 출력하도록 프로그래밍된 컴퓨터는 I, O, I, O를 차례로 출력하므로 최종 문자열은 IOIO가 된다.

컨퍼런스 주최 측은 행사마다 정확히 한 대의 컴퓨터로 홍보한다. 각 컴퓨터는 자기 행사 이름을 0번 이상 출력할 수 있다. 또한 모든 컴퓨터가 같은 횟수만큼 출력하도록 프로그래밍되어 있을 필요는 없다.

컴퓨터가 모두 출력을 마쳤는데, 안타깝게도 전부 같은 전광판에 출력했다. 컴퓨터가 동시에 출력했으므로 최종 출력 문자열에서는 행사 이름이 서로 뒤섞여 있을 수 있다. 이 문자열이 어떤 방식으로 만들어졌을 수 있는지 생각해 보자.

예를 들어 문자열 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는 올바른 입력이 아니다.

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다. 다음 T개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 테스트 케이스는 문자 I, O, i, o로만 이루어진 문자열 S이다.

출력

각 테스트 케이스마다 Case #x: y를 한 줄에 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 설명한 대로 IO가 홍보되었을 수 있는 최대 횟수이다.

제한

$1 \le T \le 100$
S의 길이는 짝수이다.
위 규칙에 맞는 해석이 적어도 하나 있다. (즉, 각 문자를 네 컴퓨터 중 하나에 배정하되, 각 컴퓨터에 배정된 문자를 순서대로 이은 부분 문자열이 그 컴퓨터의 행사 이름을 0번 이상 반복한 것이 되게 하는 방법이 있다.)

힌트

예제의 Case #1은 문제 본문에서 설명한 경우이다. (Interleaved Output: Part 1을 읽었다면, 그 문제의 첫 번째 예제 케이스와 입력은 같지만 출력은 다르다는 점에 주목하자.)

예제의 Case #2에서 IO가 두 번 홍보되었을 수는 없다. 그러려면 IO 컴퓨터가 I를 연속으로 두 번 출력해야 하기 때문이다. 하지만 IO가 한 번 홍보되었을 수는 있다. 예를 들면 다음과 같다.

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

예제의 Case #3에서는 IO가 홍보되었을 수 없다. 두 번째 문자 o는 첫 번째 문자 I를 출력한 컴퓨터가 출력한 것이어야 한다.

예제의 Case #4처럼 문자열에 I나 O가 아예 나타나지 않을 수도 있다.

예제의 Case #5에서는 IO가 최대 세 번 홍보되었을 수 있다. (이때 io는 한 번 홍보된다.)