Interleaved Output: Part 1

이 문제를 풀기 위해 Interleaved Output: Part 2 문제를 읽을 필요는 없다. Part 1과 Part 2는 처음 두 문단(이 안내문 제외)이 같다. 두 문제의 결정적인 차이는 기울임꼴로 표시한 문장이다.

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

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

콘퍼런스 주최 측이 이 컴퓨터를 쓴다는 사실은 알지만, 각 행사를 광고하는 컴퓨터가 몇 대인지는 모른다. 각 행사마다 그 이름을 출력하도록 프로그래밍된 컴퓨터는 몇 대든(0대 포함) 있을 수 있다. 또한 모든 컴퓨터가 같은 횟수만큼 출력하도록 프로그래밍된 것도 아니다. 예를 들어 Io를 한 번씩 출력하는 컴퓨터 세 대와 Io를 두 번 출력하는 컴퓨터 한 대가 있을 수도 있다.

모든 컴퓨터가 출력을 마쳤는데, 안타깝게도 전부 같은 전광판에 출력했다! 컴퓨터들이 동시에 출력했기 때문에 최종 출력 문자열에서 행사 이름이 서로 섞여 있을 수 있다. 여러분은 이 문자열이 만들어질 수 있었던 방법을 따져 보려고 한다.

예를 들어 문자열 IiOioIoO는 다음과 같이 컴퓨터 두 대로 만들어질 수 있다.

• A: Io를 두 번 출력하도록 프로그래밍됨
• B: iO를 두 번 출력하도록 프로그래밍됨

    index:  1 2 3 4 5 6 7 8
    A:      I . . . o I o .
    B:      . i O i . . . O
    string: I i O i o I o O

이 해석에서 Io 행사는 두 번, iO 행사도 두 번 광고되었고 나머지 두 행사는 한 번도 광고되지 않았다.

그런데 이 문자열은 컴퓨터 세 대로도 만들어질 수 있다.

• A: IO를 두 번 출력하도록 프로그래밍됨
• B: io를 한 번 출력하도록 프로그래밍됨
• C: io를 한 번 출력하도록 프로그래밍됨

    index:  1 2 3 4 5 6 7 8
    A:      I . O . . I . O
    B:      . i . . o . . .
    C:      . . . i . . o .
    string: I i O i o I o O

이 해석에서 IO 행사는 두 번, io 행사도 두 번 광고되었고 나머지 두 행사는 한 번도 광고되지 않았다. 이 해석에는 io를 출력하는 컴퓨터가 두 대 필요하다는 점에 주의하자. io를 두 번 출력하는 컴퓨터 한 대로는 불가능하다. 그 컴퓨터가 i를 연달아 두 번 출력해야 하는데, 이는 허용되지 않기 때문이다.

최종 출력 문자열이 주어질 때, IO 행사가 광고되었을 수 있는 횟수의 최댓값을 구하라.

문자열에는 올바른 해석이 적어도 하나 있음이 보장된다. 예를 들어 oI나 IOI는 올바른 입력이 아니다.

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

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

• 1 ≤ T ≤ 100
• S의 길이는 짝수이다.
• S의 모든 접두사 S'에 대해, S'에 있는 i의 개수와 I의 개수의 합은 o의 개수와 O의 개수의 합보다 작지 않다.
• S에 있는 i의 개수와 I의 개수의 합은 o의 개수와 O의 개수의 합과 같다.
• (위의 세 조건은 S에 문제의 규칙에 맞는 해석이 적어도 하나 있음을 보장한다.)

예제의 1번 케이스는 문제 설명에 나온 문자열이다. IO가 두 번 광고된 해석이 있음을 앞에서 보았다. 문자열에 I와 O가 두 개씩밖에 없으므로 답은 이보다 클 수 없다.

2번 케이스에서는 IO가 두 번 광고되는 것이 불가능하다. 가능한 해석은 다음뿐이다.

• A: IO를 한 번 출력하도록 프로그래밍됨
• B: iO를 한 번 출력하도록 프로그래밍됨
• C: Io를 한 번 출력하도록 프로그래밍됨

    index:  1 2 3 4 5 6
    A:      I . . O . .
    B:      . i O . . .
    C:      . . . . I o
    string: I i O O I o

또는 같은 구성으로 다음과 같이 출력된 경우이다.

    index:  1 2 3 4 5 6
    A:      I . O . . .
    B:      . i . O . .
    C:      . . . . I o
    string: I i O O I o

두 해석 모두 IO는 한 번만 광고되었다.

3번 케이스에서는 IO가 광고된 해석이 존재하지 않는다. Io를 한 번 출력하는 컴퓨터가 한 대 있어야 하고, iO를 두 번 출력하는 컴퓨터 한 대 또는 iO를 한 번씩 출력하는 컴퓨터 두 대가 있어야 한다.

4번 케이스처럼 문자열에 I나 O가 하나도 없을 수도 있다.

5번 케이스에서 IO가 네 번 광고되는 해석에는 컴퓨터 네 대가 필요하며, 각 컴퓨터는 IO를 한 번 출력하도록 프로그래밍되어 있다.