팬케이크의 역습 (Small)

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

당신은 근무 중인 수석 웨이터이고, 방금 주방에서 손님에게 낼 팬케이크 한 더미를 받았다. 유능한 팬케이크 서버답게 당신은 팬케이크를 꿰뚫어 보는 투시력이 있어서, 더미 속 각 팬케이크가 웃는 면이 위인지 빈 면이 위인지 볼 수 있다. 모든 팬케이크가 웃는 면이 위를 향한 채로 나가야 손님이 가장 기뻐할 것이다.

당신이 아는 동작은 다음과 같다. 더미 맨 위에서부터 팬케이크 몇 장(전부일 수도 있다)을 조심스럽게 들어 올리고, 그 묶음 전체를 뒤집은 다음, 들어 올리지 않은 팬케이크 위에 다시 내려놓는다. 묶음을 뒤집을 때는 한 번의 동작으로 묶음 전체를 뒤집으며, 팬케이크를 한 장씩 따로 뒤집지 않는다. 엄밀하게 말하면, 팬케이크에 위에서부터 차례로 $1, 2, \ldots, N$의 번호를 붙였을 때 맨 위의 $i$장을 골라 뒤집는다. 뒤집은 뒤 더미는 위에서부터 $i, i-1, \ldots, 2, 1, i+1, i+2, \ldots, N$ 순서가 된다. 팬케이크 $1, 2, \ldots, i$는 위를 향한 면이 반대로 바뀌고, 팬케이크 $i+1, i+2, \ldots, N$은 위를 향한 면이 그대로다.

예를 들어 웃는 면을 +, 빈 면을 -로 나타내고, 더미가 위에서부터 --+-라고 하자. 맨 위 세 장을 들어 올려 묶음 전체를 뒤집고, 남은 네 번째 팬케이크(제자리에 그대로 있고 바뀌지 않는다) 위에 다시 내려놓는 것은 올바른 동작이다. 그러면 더미는 -++-가 된다. 이 밖에 올바른 동작은 맨 위 한 장, 맨 위 두 장, 네 장 전부를 뒤집는 것이다. 반면 가운데 두 장이나 맨 아래 한 장만 골라 뒤집는 것은 올바른 동작이 아니다. 항상 맨 위에서부터 몇 장을 가져가야 한다.

모든 팬케이크가 웃는 면이 위를 향하기 전에는 손님에게 내지 않는다. 하지만 팬케이크가 식으면 안 되므로 서둘러야 한다. 최선의 선택을 한다면, 모든 팬케이크의 웃는 면이 위를 향하게 하려면 동작을 최소 몇 번 해야 할까?

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 이어서 $T$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 문자열 $S$ 하나로 이루어진 한 줄이다. $S$의 각 문자는 +(처음에 웃는 면이 위인 팬케이크) 또는 -(처음에 빈 면이 위인 팬케이크)이다. 문자열을 왼쪽에서 오른쪽으로 읽으면 더미를 위에서 아래로 본 모습이 된다.

제한

• $1 \le T \le 100$
• $S$의 모든 문자는 + 또는 -이다.
• $1 \le$ ($S$의 길이) $\le 10$

각 테스트 케이스마다 Case #x: y 형식의 한 줄을 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 모든 팬케이크의 웃는 면이 위를 향하게 하는 데 필요한 동작의 최소 횟수이다.

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

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

3번 케이스에서는 동작을 두 번 해야 한다. 최적의 방법 하나는 첫 번째 팬케이크만 뒤집어 더미를 --로 만든 다음, 두 장을 모두 뒤집어 ++로 만드는 것이다. 맨 아래 팬케이크만 따로 뒤집어서 한 번에 끝낼 수는 없다는 점에 주의하라. 동작을 할 때마다 맨 위에서부터 시작하는 묶음을 골라야 한다.

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

5번 케이스의 올바른 방법 하나는 먼저 더미 전체를 뒤집어 +-++를 만들고, 맨 위 팬케이크를 뒤집어 --++를 만든 다음, 마지막으로 맨 위 두 장을 뒤집어 ++++를 만드는 것이다.