뒤섞인 출력: 파트 2

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

목성의 어느 먼 위성에서 개발자 회의 행사 몇 개가 곧 열린다! 이 행사들의 이름은 IO(대문자 I, 대문자 O), Io(대문자 I, 소문자 o), iO(소문자 I, 대문자 O), 그리고 io(소문자 I, 소문자 O)이다.

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

회의 주최 측이 각 행사를 광고하기 위해 정확히 한 대의 컴퓨터를 사용한다는 사실을 알고 있다. 각 프린터는 자신의 행사 이름을 영 번 이상 인쇄할 수 있다. 또한 모든 컴퓨터가 반드시 같은 횟수만큼 인쇄하도록 프로그래밍된 것은 아니다.

모든 컴퓨터가 인쇄를 마쳤지만, 안타깝게도 모두 같은 화면에 인쇄했다! 컴퓨터들이 동시에 인쇄했으므로 최종 출력 문자열에서 행사 이름들이 서로 뒤섞였을 수 있다. 이 문자열이 만들어졌을 수 있는 가능한 방법들을 살펴보고자 한다.

예를 들어, 문자열 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는 유효한 입력이 아니다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. 1 ≤ T ≤ 100. S의 길이는 짝수이다. 위 규칙과 일치하는 문자열의 해석이 적어도 하나 존재한다. (즉, 각 문자를 네 대의 컴퓨터 중 하나에 할당하여, 각 컴퓨터에 해당하는 부분 문자열이 그 컴퓨터의 행사 이름을 영 번 이상 반복한 것으로 이루어지게 하는 방법이 존재한다.)

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

2 ≤ S의 길이 ≤ 8.

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

2 ≤ S의 길이 ≤ 100.

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

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

예제 케이스 #1은 문제 설명에서 다룬 케이스이다. (뒤섞인 출력: 파트 1를 읽었다면, 이 입력이 그 문제의 첫 예제 케이스와 같지만 출력은 다르다는 점에 유의하라.)

예제 케이스 #2에서는 IO가 두 번 광고되었을 수 없다. 그러려면 IO 컴퓨터가 I를 연속으로 두 번 인쇄했어야 하기 때문이다. 하지만 다음과 같이 IO가 한 번 광고되었을 가능성은 있다.

예제 케이스 #3에서는 IO가 광고되었을 수 없다는 점에 유의하라. 두 번째 문자인 o는 첫 번째 문자 I를 인쇄한 컴퓨터와 같은 컴퓨터가 인쇄했어야 한다.

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

예제 케이스 #5에서는 IO가 최대 세 번까지 광고되었을 가능성이 있다(이 경우 io는 한 번 광고되었다).