반박할 수 없는 결과

이자벨라와 올가가 번갈아 가며 하는 게임이다. 이자벨라가 먼저 둔다. 게임은 모든 말이 한 줄로 놓인 상태에서 시작한다. 말은 남색과 주황색 두 가지 색이다. 이자벨라의 차례에는 남은 말 중 가장 왼쪽이나 가장 오른쪽에 있는 남색 말을 하나 골라 제거해야 한다. 올가의 차례에는 가장 왼쪽이나 가장 오른쪽에 있는 주황색 말을 하나 골라 제거해야 한다. 어느 순간이든 한 플레이어가 둘 수 있는 합법적인 수가 없으면(말이 하나도 남지 않은 경우를 포함한다) 그 플레이어가 진다. 이때 상대는 1점에, 판에 남은 말 하나당 1점을 더해 얻는다.

남색 말은 대문자 I, 주황색 말은 대문자 O로 나타낸다. 예를 들어 시작 판이 IOIOOOII라고 하자.

이자벨라는 첫 차례에 왼쪽 끝 말이든 오른쪽 끝 말이든 고를 수 있다. 둘 다 남색이기 때문이다. 왼쪽 끝 말을 제거했다고 하자. 그러면 판은 OIOOOII가 된다. 올가는 새 왼쪽 끝 말을 제거할 수밖에 없다. 오른쪽 끝 말은 주황색이 아니기 때문이다. 판은 IOOOII가 된다. 이자벨라는 다시 고를 수 있고, 이번에는 오른쪽 끝 말을 제거해 IOOOI를 올가에게 넘긴다. 이 시점에 올가는 둘 수 있는 수가 없으므로 이자벨라가 이긴다. 남은 말이 5개이므로 이자벨라는 총 $1+5=6$점을 얻는다.

각 플레이어는 이기기 위해, 그리고 자기 점수를 최대화하기 위해 최선을 다해 둔다. 이길 수 없다고 판단한 플레이어는 상대의 점수를 최소화하는 방향으로 둔다.

시작 판이 주어졌을 때 누가 이기고 그 점수가 얼마인지 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다. 이후 $T$개의 줄에 테스트 케이스가 하나씩 주어진다. 각 줄에는 판의 상태를 나타내는 문자열 $B$가 있다. $B$의 왼쪽에서 $i$번째 문자가 남색 말이면 I, 주황색 말이면 O이다.

각 테스트 케이스마다 Case #x: y z 형식으로 한 줄을 출력한다. $x$는 테스트 케이스 번호(1부터 시작), $y$는 승자의 이니셜(이자벨라는 I, 올가는 O), $z$는 승자가 얻는 점수다.

• $1 \le T \le 100$.
• $B$의 각 문자는 대문자 I 또는 대문자 O이다.

1번 예제에서 이자벨라는 문제 본문의 예보다 나은 수를 둘 수 있다. 처음에 오른쪽 끝 말을 제거하면 올가는 둘 수 있는 수가 없고, 이자벨라는 말 7개가 남은 상태로 이긴다. 이자벨라는 총 $1+7=8$점을 얻는다.

2번 예제에서 이자벨라는 첫 수조차 둘 수 없으므로 올가가 이긴다.

3번 예제에서는 두 플레이어 모두 둘 수 있는 수가 하나뿐이고, 말이 모두 없어질 때까지 게임이 진행되어 올가가 이긴다. 올가가 얻는 점수는 1점뿐이다.

4번 예제에서도 게임이 끝날 때 말이 모두 없어지지만, 승자는 이자벨라다.