크레인 트럭 (라지)

큰 창고에 보관 자리 240개가 원형으로 놓여 있다.

크레인을 실은 트럭이 이 원을 따라 움직이면서 프로그램에 적힌 대로 상자를 집거나 내려놓는다. 트럭에는 상자가 무한히 실려 있어서 언제든지 상자를 하나 더 내려놓을 수 있다.

프로그램은 다음 명령을 나열한 것이다.

• b : 한 자리 뒤로 이동한다.
• f : 한 자리 앞으로 이동한다.
• u : 지금 있는 자리에서 상자를 하나 집는다.
• d : 지금 있는 자리에 상자를 하나 내려놓는다.
• ( : 아무것도 하지 않는다.
• ) : 지금 있는 자리에 상자가 두 개 이상 있으면 프로그램에서 앞쪽으로 가장 가까운 ( 로 돌아가 그 자리부터 실행을 이어 간다. 이때 트럭은 움직이지 않는다.

( 와 ) 는 항상 짝을 이루어서, ( 가 나오면 뒤쪽에 짝이 되는 ) 가 반드시 나온다. 한 프로그램에 들어가는 짝은 많아야 두 개이고, 두 개여도 서로 겹치지 않는다. 나올 수 있는 모양은 다음 세 가지뿐이다.

• ( 도 ) 도 없다.
• ( 가 하나 나오고 그 뒤에 ) 가 하나 나온다.
• (, ), (, ) 가 이 순서로 나온다.

트럭이 프로그램을 시작하기 전에 모든 보관 자리에는 상자가 하나씩 놓여 있다.

트럭이 어떤 자리에서 마지막 상자를 집으면 곧바로 다른 트럭이 와서 그 자리에 상자 256개를 내려놓는다. 반대로 트럭이 상자를 내려놓아 그 자리의 상자가 257개가 되면 다른 트럭이 지나가면서 256개를 가져가고 하나만 남긴다. 그래서 모든 자리의 상자 개수는 언제나 1개 이상 256개 이하다.

트럭은 프로그램이 끝날 때까지 앞이나 뒤로 몇 번 움직이는가?

첫 줄에 테스트 케이스의 개수 $T$가 주어진다.

다음 $T$개 줄에 크레인 트럭 프로그램이 한 줄에 하나씩 주어진다.

각 테스트 케이스마다 Case #X: Y 형식으로 한 줄씩 출력한다. $X$는 테스트 케이스 번호이고 $Y$는 트럭이 움직인 횟수다.

• $1 \le T \le 20$
• 프로그램의 길이는 1자 이상 2000자 이하다.
• 프로그램은 b, f, u, d, (, ) 문자로만 이루어진다.
• 프로그램은 반드시 끝난다.
• 한 프로그램에서 ( 와 ) 의 짝은 많아야 두 개이고, 서로 겹치지 않는다.