팬케이크의 복수 (Large)

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

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

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

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

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

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

제한

• 1 ≤ T ≤ 100
• S의 모든 문자는 + 또는 -이다.
• 1 ≤ S의 길이 ≤ 100

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

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

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

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

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

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