조교

서로 다른 유형의 문제 세트로 평가되는 프로그래밍 강의를 수강하고 있다. 강의는 양의 짝수 일수 동안 진행된다. 강의를 시작할 때는 가진 문제 세트가 없다. 강의가 진행되는 각 날에는 다음 중 정확히 하나를 해야 한다.

• "Coding" 문제 세트를 요청한다.

• "Jamming" 문제 세트를 요청한다.

• 채점을 위해 문제 세트를 제출한다. 이 선택지를 고르려면 적어도 하나의 문제 세트를 가지고 있어야 한다. 문제 세트가 여러 개라면 유형과 관계없이 그중 가장 최근에 요청한 것을 제출해야 한다.

모든 문제 세트는 서로 다르다. 각 유형의 문제 세트를 몇 개씩 제출해야 한다는 조건은 없다. 문제 세트를 제출하면 더 이상 그 문제 세트를 가지고 있지 않게 된다. 강의가 끝나기 전에 제출하지 않은 문제 세트에서는 점수를 얻지 못한다.

문제 세트는 인공지능 조교에게 요청하고 제출한다. 이상하게도 조교에게는 여러 기분이 있으며, 각 날에는 "Coding" 또는 "Jamming"에 대한 기분이다.

• 문제 세트를 요청할 때:

• 요청한 주제가 조교의 기분과 일치하면, 최대 10점짜리 문제 세트를 배정한다.

• 요청한 주제가 조교의 기분과 일치하지 않으면, 최대 5점짜리 문제 세트를 배정한다.

• 문제 세트를 제출할 때:

• 제출한 문제 세트의 주제가 그날 조교의 기분과 일치하면, 그 문제 세트의 최대 점수를 준다.

• 제출한 문제 세트의 주제가 그날 조교의 기분과 일치하지 않으면, 그 문제 세트의 최대 점수보다 5점 적게 준다.

예를 들면 다음과 같다.

• 조교가 "Coding"에 대한 기분인 날에 "Coding" 문제 세트를 요청하고, 조교가 "Jamming"에 대한 기분인 날에 이를 제출하면 5점을 얻는다. 이 문제 세트의 최대 점수는 10점이지만, 조교가 그보다 5점 적게 주기 때문이다.

• 조교가 "Coding"에 대한 기분인 날에 "Jamming" 문제 세트를 요청하고, 조교가 "Jamming"에 대한 기분인 날에 이를 제출하면 5점을 얻는다. 이 문제 세트의 최대 점수는 5점이며, 조교가 최대 점수를 주기 때문이다.

조교를 매우 잘 이해하는 선배의 도움 덕분에, 강의가 진행되는 각 날에 조교가 어떤 기분일지 알고 있다. 얻을 수 있는 총점의 최댓값은 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. S의 길이는 짝수이다.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ S의 길이 ≤ 50.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ S의 길이 ≤ 20000. 데이터 세트에 있는 모든 S의 길이의 합은 최대 150000이다.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어지며, 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 C 및/또는 J 문자로 이루어진 문자열 S가 있는 한 줄로 구성된다. S의 i번째 문자는 강의 i번째 날의 조교 기분을 나타낸다. 문자가 C이면 조교는 "Coding"에 대한 기분이고, 문자가 J이면 "Jamming"에 대한 기분이다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 1부터 시작하는 테스트 케이스 번호이고, y는 해당 테스트 케이스에서 얻을 수 있는 점수의 최댓값이다.

예제 케이스 #1에서는 다음 전략이 최적이다. 1일째: "Coding" 문제 세트를 요청한다(이를 C1라고 부른다). 2일째: C1을 제출한다. 3일째: "Jamming" 문제 세트를 요청한다(이를 J1라고 부른다). 4일째: J1을 제출한다.

예제 케이스 #2, #3, #4에서는 다음 전략이 최적이다. C1을 요청하고, J1을 요청하고, J1을 제출하고, C1을 제출한다.

예를 들어 케이스 #2에서는 C1을 요청하고, J1을 요청한 다음, C1을 제출할 수 없다는 점에 유의하라. 가장 최근에 요청한 문제 세트만 제출할 수 있다.

예제 케이스 #5에서는 하루에 "Coding" 문제 세트를 요청하고 다음 날에 이를 제출하는 과정을 번갈아 할 수 있다.