크레인 트럭

여러분은 원형으로 배치된 $2^{40}$개의 보관 위치가 있는 대형 보관 시설에 있다.

크레인이 달린 트럭이 보관 위치들의 원을 따라 움직이며, 프로그램에 따라 상자를 들어 올리거나 내려놓는다. (트럭에는 상자가 무제한으로 실려 있으므로 언제든 상자를 더 내려놓을 수 있다.)

프로그램은 다음 명령들의 수열로 구성된다.

• b : 한 위치 뒤로 이동한다

• f : 한 위치 앞으로 이동한다

• u : 현재 위치에서 상자 하나를 들어 올린다

• d : 현재 위치에 상자 하나를 내려놓는다

• ( : 아무것도 하지 않는다

• ) : 현재 위치에 상자가 하나보다 많으면 명령 수열에서 가장 최근의 (로 돌아가 그곳부터 프로그램을 계속한다. (이 명령은 트럭을 움직이지 않는다.) 프로그램의 (와 ) 명령은 항상 쌍을 이룬다. 즉, ( 뒤에는 나중에 그와 짝을 이루는 )가 나온다. 프로그램에는 이러한 쌍이 최대 두 개 있으며, 두 쌍이 있다면 중첩되지 않는다. 즉, 다음 중 하나이다.

• ( 또는 ) 명령이 없다.

• 프로그램의 어딘가에 ( 명령 하나가 있고, 나중에 ) 명령 하나가 나온다.

• ( 명령이 있고, 나중에 ) 명령이 나오며, 그보다 나중에 또 다른 (가 나오고, 다시 그보다 나중에 또 다른 )가 나온다.

예제 케이스에는 이들 각각의 예가 들어 있다.

크레인 트럭이 프로그램 실행을 시작하기 전에 각 보관 위치에는 상자 하나가 놓여 있다.

기이하게도 트럭이 어떤 위치의 마지막 상자를 들어 올리면 다른 트럭이 즉시 와서 그곳에 상자 256개를 내려놓는다! 마찬가지로 트럭이 어떤 위치에 상자를 내려놓아 그 위치의 상자가 257개가 되면 다른 트럭이 즉시 지나가면서 상자 중 256개를 들어 올리고 하나만 남긴다! 따라서 모든 위치에는 항상 1개에서 256개 사이의 상자가 있다.

트럭이 프로그램의 끝에 도달하기 전에 앞이나 뒤로 몇 번 이동하는가?

제한

메모리 제한: 1 GB. 1 ≤ T ≤ 20. 1 ≤ 프로그램의 길이 ≤ 2000. 프로그램은 종료되는 것이 보장된다.

작은 데이터 세트

시간 제한: 240초. 프로그램에는 (와 ) 명령의 쌍이 최대 하나 포함된다.

큰 데이터 세트

시간 제한: 480초. 프로그램에는 (와 ) 명령의 쌍이 최대 두 개 포함된다.

프로그램의 테스트 케이스 수인 정수 T를 포함하는 한 줄이 주어진다.

이어서 T개의 줄이 주어지며, 각 줄에는 최대 2000개의 문자로 이루어진 크레인 트럭 프로그램이 들어 있다.

각 테스트 케이스에 대해 한 줄씩 총 T개의 줄에 "Case #X: Y"을 출력한다. 여기서 X는 테스트 케이스 번호이고, Y는 트럭이 이동한 횟수이다.