조각 프로젝트

어릴 때부터 조각가였던 다빈치는 많은 조각을 설계했지만, 그중 완성된 것은 거의 없었고 웃는 아기와 성모자 하나만이 남았다. 이 조각을 완성하는 데 다빈치는 오랜 시간과 많은 재료를 들였다.

다빈치는 이 프로젝트의 첫 단계에 n일을 쓰기로 했다. 처음에 다빈치에게는 조각할 재료가 없었다. 그는 매일 하루를 쉬며(‘o’로 표시) 시장에 가서 재료 1단위를 사거나, 작업하며(‘w’로 표시) 조각에 재료 1단위를 소비했다. 그러나 일정을 짜고 나서 다빈치는 그것이 현실적이지 않다는 것을 알았다. 어떤 작업일에는 조각할 재료가 전혀 없을 수도 있고, 마지막에는 쓰지 않은 재료가 남을 수도 있었다. 조각 프로젝트를 순조롭게 진행하기 위해 다빈치는 특정 날의 활동 일부를 취소하기로 했고, 그 조건은 다음과 같다.

1. 재료 없이 시작해서, 다빈치는 각 작업일에 조각할 재료를 적어도 1단위 가지고 있어야 한다.
2. n일 후에 다빈치에게 남는 재료가 없어야 한다.
3. 취소하는 활동의 수가 최소여야 한다. (다빈치는 원래 일정을 너무 많이 고치고 싶지 않았다!)

다빈치는 취소해야 하는 활동의 최소 수를 알고 싶어 한다.

첫 줄에는 파일에 들어 있는 입력 데이터 세트의 수 1 ≤ K ≤ 10이 주어진다. 그다음 K개의 데이터 세트가 다음 형식으로 주어진다.

각 데이터 세트는 다빈치의 원래 일정을 나타내는 비어 있지 않은 문자열 S 하나로 이루어진 한 줄로 주어진다. S의 길이는 최대 1000이고 ‘w’와 ‘o’로만 이루어져 있다. S의 길이를 읽어 n을 구할 수 있다.

각 데이터 세트마다 먼저 “Data Set x:”를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호이다.

그다음 일정을 실행 가능하게 만들기 위해 다빈치가 취소해야 했던 활동의 최소 수를 출력한다. 다빈치가 활동을 하나도 취소하지 않아도 되는 경우도 있다.

각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.