팬케이크의 복수

무한 팬케이크 하우스에서 방금 새로운 종류의 팬케이크를 선보였다! 이 팬케이크는 한쪽 면에 초콜릿 칩으로 만든 웃는 얼굴(이하 "행복한 면")이 있고, 반대쪽 면(이하 "빈 면")에는 아무것도 없다.

당신은 당번 수석 웨이터이며, 주방에서 방금 손님에게 내놓을 팬케이크 한 더미를 건네주었다. 훌륭한 팬케이크 담당자라면 누구나 그렇듯, 당신은 팬케이크를 투시하는 눈을 갖고 있어 더미의 각 팬케이크에서 행복한 면과 빈 면 중 어느 쪽이 위를 향하고 있는지 볼 수 있다. 당신은 팬케이크를 내놓을 때 모든 팬케이크의 행복한 면이 위를 향하고 있으면 손님이 가장 행복해할 것이라고 생각한다.

당신은 다음과 같은 동작을 알고 있다. 더미의 맨 위에서 일정한 수의 팬케이크를 조심스럽게 들어 올리고(전부를 들어 올려도 된다), 그 묶음 전체를 뒤집은 다음, 들어 올리지 않은 팬케이크가 있다면 그 위에 묶음을 다시 내려놓는다. 팬케이크 묶음을 뒤집을 때는 묶음 전체를 한 번의 동작으로 뒤집으며, 각 팬케이크를 개별적으로 뒤집지 않는다. 형식적으로, 팬케이크에 위에서 아래까지 1, 2, ..., N의 번호를 매겼다면, 맨 위의 i개 팬케이크를 뒤집도록 선택한다. 그러면 뒤집은 뒤의 더미는 i, i-1, ..., 2, 1, i+1, i+2, ..., N이 된다. 이제 팬케이크 1, 2, ..., i는 이전과 반대쪽 면이 위를 향하지만, 팬케이크 i+1, i+2, ..., N은 이전에 위를 향하던 것과 같은 면이 위를 향한다.

예를 들어, 행복한 면을 +로, 빈 면을 -로 나타내자. 위에서 시작한 더미가 --+-라고 하자. 이 동작을 유효하게 수행하는 한 가지 방법은 맨 위의 세 장을 들어 올리고, 묶음 전체를 뒤집은 뒤, 남은 네 번째 팬케이크 위에 다시 내려놓는 것이다(네 번째 팬케이크는 제자리에 그대로 있으며 변하지 않는다). 그러면 더미의 새로운 상태는 -++-가 된다. 그 밖의 유효한 방법으로는 맨 위의 한 장, 맨 위의 두 장 또는 네 장 모두를 들어 올려 뒤집는 방법이 있다. 예를 들어, 가운데 두 장이나 맨 아래의 한 장을 선택해 뒤집는 것은 유효하지 않다. 맨 위에서부터 일정한 수만큼만 가져갈 수 있다.

모든 팬케이크의 행복한 면이 위를 향하기 전에는 손님에게 내놓지 않을 것이지만, 팬케이크가 식는 것은 원하지 않으므로 빠르게 움직여야 한다! 최적의 선택을 할 때, 모든 팬케이크의 행복한 면이 위를 향하게 만들기 위해 이 동작을 수행해야 하는 최소 횟수는 얼마인가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. S의 모든 문자는 + 또는 -이다.

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

1 ≤ S의 길이 ≤ 10.

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

1 ≤ S의 길이 ≤ 100.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 문자열 S가 있는 한 줄로 이루어지며, 각 문자는 +(처음에 행복한 면이 위를 향하는 팬케이크를 나타냄) 또는 -(처음에 빈 면이 위를 향하는 팬케이크를 나타냄)이다. 이 문자열을 왼쪽에서 오른쪽으로 읽으면 위에서 아래로 바라본 더미를 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이고(1부터 시작), y는 모든 팬케이크의 행복한 면이 위를 향하게 만들기 위해 이 동작을 수행해야 하는 최소 횟수이다.

케이스 #1에서는 첫 번째이자 유일한 팬케이크를 뒤집어 동작을 한 번만 수행하면 된다.

케이스 #2에서는 첫 번째 팬케이크만 뒤집어 동작을 한 번만 수행하면 된다.

케이스 #3에서는 동작을 두 번 수행해야 한다. 한 가지 최적해는 먼저 첫 번째 팬케이크만 뒤집어 더미를 --로 바꾼 다음, 두 팬케이크를 모두 뒤집어 더미를 ++로 바꾸는 것이다. 맨 아래의 팬케이크만 개별적으로 뒤집어 한 번의 동작으로 해결할 수는 없다는 점에 유의하라. 동작을 수행할 때마다 맨 위에서 시작하는 더미를 선택해야 한다.

케이스 #4에서는 모든 팬케이크의 행복한 면이 이미 위를 향하고 있으므로 아무것도 할 필요가 없다.

케이스 #5에서 한 가지 유효한 해법은 먼저 팬케이크 더미 전체를 뒤집어 +-++를 만들고, 그다음 맨 위의 팬케이크를 뒤집어 --++를 만든 뒤, 마지막으로 맨 위의 두 팬케이크를 뒤집어 ++++를 만드는 것이다.