Crane Truck (Small)

Time limit10sMemory limit512 MB

Summary

Run each crane program on 240 circular cells with wrapping crate counts and count the truck's forward and backward moves.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

A storage yard has 240 storage locations arranged in a circle. A truck with a crane on it drives around the circle and picks up or puts down crates according to a program. The truck carries an unlimited supply of crates, so it can always put another crate down.

A program is a sequence of these instructions:

b: move back one location
f: move forward one location
u: pick up one crate at the current location
d: put down one crate at the current location
(: do nothing
): if the current location holds more than one crate, go back to the most recent ( in the program and continue from there. The truck itself does not move.

Every ( has a matching ) later in the program. A program holds at most two such pairs, and the pairs are never nested. A program therefore has one of three shapes: no ( and no ) at all, one ( followed later by one ), or (, ), (, ) in that order.

Before the truck starts, every location holds exactly one crate. All locations look the same at that moment, so the answer does not depend on which location the truck starts at.

If the truck picks up the last crate at a location, another truck instantly arrives and puts down 256 crates there. If the truck puts a crate down and the location then holds 257 crates, another truck instantly drives past, picks up 256 of them and leaves one behind. Every location therefore always holds between 1 and 256 crates.

Count how many times the truck moves forward or backward before its program ends.

Input

The first line holds an integer $T$ , the number of programs.

Each of the next $T$ lines holds one program.

Limits

$1 \le T \le 20$
$1 \le$ (length of a program) $\le 2000$
A program uses only the characters b, f, u, d, ( and ).
Every program halts.
A program holds at most two pairs of ( and ), and the pairs are never nested.
Running all $T$ programs executes at most $2 \times 10^6$ instructions in total.

Output

Print $T$ lines. For the $i$ -th program print Case #i: Y, where $Y$ is the number of times the truck moves forward or backward.

Examples3

Example 1

Input

4
ufffdddbbbdd
dddd(fdbu)fff
dddd(fdddddbu)f(fdddddbu)
bf

Expected output

Case #1: 6
Case #2: 11
Case #3: 49
Case #4: 2

Example 2

Input

5
f
b
dddd
u
d(u)

Expected output

Case #1: 1
Case #2: 1
Case #3: 0
Case #4: 0
Case #5: 0

Example 3

Input

2
dd(ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffu)
bffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffb

Expected output

Case #1: 480
Case #2: 242