종이 접기

길고 곧은 종이 띠가 하나 있다. 우리는 접기 연산 을 여러 번 수행한다. 한 번의 접기 연산에서는 긴 변에 수직인 접는 선 하나를 고르고, 그 선을 지나는 현재 겹쳐진 모든 층 을 한꺼번에 접는다. 일부 층만 접는 것은 허용되지 않는다.

접기를 여러 번 한 뒤 종이를 완전히 펼쳐서 긴 변을 따라 살펴보면, 접힌 자국(주름)들은 일정한 간격으로 놓여 띠를 합동인 여러 조각(stripe) 으로 나눈다. 띠를 한쪽 끝에서 반대쪽 끝까지 읽어 나가면 각 주름은 두 방향 중 하나로 꺾이며, 이를 문자 A 또는 V 로 나타낸다.

또한 완전히 접힌 상태에서 띠의 길이는 정확히 한 조각의 길이와 같다. 즉, 모든 조각이 위아래로 포개진다(두께는 무시한다).

완전히 펼친 상태에서 관찰되는 주름들의 수열이 주어질 때, 평평한 띠로부터 이 수열을 만들기 위해 필요한 접기 연산의 최소 횟수 를 구하여라.

한 번의 접기 연산이 여러 개의 주름을 동시에 만들 수도 있다. 이전 단계에서 이미 종이의 일부가 겹쳐져 있기 때문이다. 그래도 겹친 모든 층은 함께 접힌다. 수열의 주름이 $n$ 개라면, 주름마다 차례로 한 번씩 접는 방법은 항상 가능하고 $n$ 번의 접기를 사용하지만, 이것이 최소인 경우는 보통 아니다.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 한 줄에 하나씩 주어진다. 각 줄은 띠의 긴 변을 따라 나타나는 주름을 나타내는, 문자 A 와 V 로 이루어진 비어 있지 않은 문자열이다. 각 문자열의 길이는 $200$ 미만이다. 입력은 파일의 끝에서 종료된다.

각 테스트 케이스마다, 해당 띠를 만들기 위해 필요한 접기 연산의 최소 횟수를 한 줄에 하나씩 출력한다.