반박할 수 없는 결과

Izabella와 Olga는 번갈아 차례를 진행하며 게임을 한다. Izabella가 먼저 시작한다. 게임은 모든 게임 조각이 한 줄로 놓인 상태에서 시작한다. 조각에는 남색과 주황색의 두 가지 색이 있다. Izabella의 차례에는 남아 있는 조각 중 가장 왼쪽이나 가장 오른쪽에 있는 남색 조각을 골라 제거해야 한다. Olga의 차례에는 남아 있는 조각 중 가장 왼쪽이나 가장 오른쪽에 있는 주황색 조각을 골라 제거해야 한다. 어느 시점에 한 플레이어가 합법적으로 둘 수 없다면(남은 조각이 없기 때문일 수도 있다), 그 플레이어가 게임에서 지며, 다른 플레이어는 $1$점에 더해 보드에 남아 있는 각 조각마다 $1$점을 추가로 받는다.

남색 조각은 대문자 I로, 주황색 조각은 대문자 O로 나타낸다. 예를 들어 다음과 같은 시작 보드에서 게임한다고 하자. IOIOOOII.

Izabella의 첫 차례에는 양쪽 끝 조각이 모두 남색이므로 가장 왼쪽 조각이나 가장 오른쪽 조각 중 하나를 제거할 수 있다. 가장 왼쪽 조각을 선택한다고 하자. 그러면 보드는 OIOOOII가 된다. 그다음에는 가장 오른쪽 조각이 주황색이 아니므로 Olga는 새로 가장 왼쪽이 된 조각을 제거할 수밖에 없고, IOOOII가 남는다. Izabella는 다시 선택할 수 있으며, 이번에는 가장 오른쪽 조각을 선택하여 Olga의 차례에 IOOOI를 남긴다. 이 시점에 Olga는 유효한 수를 둘 수 없으므로 Izabella가 이긴다. $5$개의 조각이 남아 있으므로 Izabella는 총 $1+5=6$점을 얻는다.

각 플레이어는 승리하고 자신의 점수를 최대화하기 위해 최적으로 플레이한다. 승리를 보장할 수 없는 플레이어는 상대의 점수를 최소화하도록 플레이한다.

시작 보드가 주어질 때, 누가 이기며 그 승자의 점수는 얼마인지 구하라.

제한

시간 제한: 20초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{B}$의 각 문자는 대문자 I 또는 대문자 O이다.

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

$2 \le$는 $\mathbf{B} \le 10$의 길이이다.

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

$2 \le$는 $\mathbf{B} \le 100$의 길이이다.

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

$2 \le$는 $\mathbf{B} \le 10^5$의 길이이다.

입력의 첫 번째 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 줄이 주어진다. 각 줄은 하나의 테스트 케이스를 나타내며, 보드의 상태를 나타내는 문자열 $\mathbf{B}$를 포함한다. $\mathbf{B}$의 $i$번째 문자는 왼쪽에서 $i$번째 조각이 남색이면 I이고, 주황색이면 O이다.

각 테스트 케이스마다 Case #$x$: $y$ $z$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), $y$는 승자의 이름 첫 글자(Izabella이면 I, Olga이면 O)이고, $z$는 승자가 얻는 점수이다.

예제 케이스 #1에서 Izabella는 문제 설명의 예보다 더 잘할 수 있다. 가장 오른쪽 조각을 제거하며 시작하면 Olga는 가능한 수가 없고, $7$개의 조각이 남은 상태로 Izabella가 이긴다. Izabella는 총 $1+7=8$점을 얻는다.

예제 케이스 #2에서 Izabella는 자신의 첫 수조차 둘 수 없으므로 Olga가 이긴다!

예제 케이스 #3에서 두 플레이어 모두 어떤 수를 둘지 선택의 여지가 없으며, 모든 조각이 소진된 뒤 Olga가 이기므로 $1$점만 얻는다.

예제 케이스 #4에서도 게임이 끝날 때 모든 조각이 소진되지만, 승리하는 쪽은 Izabella이다.