뒤섞인 출력: 파트 1

이 문제를 풀기 위해 뒤섞인 출력: 파트 2 문제를 읽을 필요는 없다. 파트 1와 파트 2는 모두 첫 두 문단이 같다(이 안내문은 포함하지 않는다). 두 파트 사이의 핵심적인 차이에는 밑줄을 그었다.

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

행사를 홍보하는 가장 좋은 방법은 행사 이름을 한 번에 한 글자씩 인쇄하고 그 출력을 디지털 디스플레이에 표시하는 특수 컴퓨터를 사용하는 것이다. 이러한 각 컴퓨터는 한 행사의 이름만 알고 있으며, 그 행사 이름을 영 번 이상 인쇄하도록 프로그래밍되어 있다. 예를 들어 IO을 두 번 인쇄하도록 프로그래밍된 컴퓨터는 I을 인쇄하고, 이어서 O을 인쇄하고, 이어서 I을 인쇄하고, 이어서 O을 인쇄하여 최종 문자열 IOIO을 만든다.

콘퍼런스 주최자들이 이러한 컴퓨터들을 사용하고 있다는 것은 알지만, 각 행사를 몇 대의 컴퓨터가 홍보하는지는 모른다. 각 행사에 대해 그 행사 이름을 인쇄하도록 프로그래밍된 컴퓨터는 임의의 수만큼(영 대를 포함하여) 있을 수 있다. 또한 모든 컴퓨터가 반드시 같은 횟수만큼 인쇄하도록 프로그래밍된 것은 아니다. 예를 들어 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은 유효한 입력이 아니다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. S의 길이는 짝수이다. S의 각 접두사 S'에 대해, S'에 있는 i 문자의 수와 I 문자의 수를 더한 값은 o 문자의 수와 O 문자의 수를 더한 값보다 작지 않다. S에 있는 i의 수와 I의 수를 더한 값은 o의 수와 O의 수를 더한 값과 같다. (위의 세 조건은 문제 설명의 규칙과 일치하는 S의 해석이 적어도 하나 존재함을 보장한다는 점에 유의하라.)

테스트 세트 1 (결과 공개)

2 ≤ S의 길이 ≤ 8.

테스트 세트 2 (결과 비공개)

2 ≤ S의 길이 ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 줄이 주어지며, 각 줄은 하나의 테스트 케이스를 나타낸다. 각 케이스는 집합 I, O, i, o에 속하는 문자만 포함하는 문자열 S로 구성된다.

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

예제 케이스 #1은 문제 설명에서 다룬 케이스이다. IO이 두 번 홍보된 해석이 있음을 확인했다. 문자열에는 I이 두 개, O이 두 개뿐이므로 답은 이보다 클 수 없다.

예제 케이스 #2에서는 IO이 두 번 홍보되었을 가능성이 없다는 점에 유의하라. 가능한 해석은 다음뿐이다.

• A: IO을 한 번 인쇄하도록 프로그래밍됨

• B: iO을 한 번 인쇄하도록 프로그래밍됨

• C: Io을 한 번 인쇄하도록 프로그래밍됨

또는 같지만 다음과 함께

이 두 해석 중 어느 것에서도 IO은 한 번만 홍보되었다.

예제 케이스 #3에서는 IO이 홍보된 해석이 존재하지 않는다. Io을 한 번 인쇄하도록 프로그래밍된 컴퓨터가 한 대 있었어야 하며, 여기에 iO을 두 번 인쇄하는 컴퓨터 한 대 또는 iO을 각각 한 번씩 인쇄하는 컴퓨터 두 대가 있었어야 한다.

예제 케이스 #4에서는 I 및/또는 O이 문자열에 아예 나타나지 않을 수도 있다는 점에 유의하라.

예제 케이스 #5에서 IO이 네 번 홍보된 해석에는 각각 IO을 한 번 인쇄하도록 프로그래밍된 컴퓨터 네 대가 필요하다.