Crane Truck (Large)

You are in a large storage facility with 240 storage locations arranged in a circle.

A truck with a crane on it moves along 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 nearest ( that appears earlier in the program and keep running from there. The truck does not move.

The ( and ) instructions always come in pairs, so every ( is followed later by a matching ). A program holds at most two such pairs, and two pairs are never nested. Only these three shapes occur.

• The program holds no ( and no ).
• One ( appears, and one ) appears later.
• One ( appears, then a ), then another (, then another ).

Every storage location holds exactly one crate before the truck starts running its program.

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

How many times does the truck move forward or backward before it reaches the end of its program?

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

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

For each test case, print one line in the form Case #X: Y, where $X$ is the test case number and $Y$ is the number of times the truck moves.

• $1 \le T \le 20$
• The length of each program is between 1 and 2000 characters.
• Each program consists only of the characters b, f, u, d, ( and ).
• Every program is guaranteed to terminate.
• Each program holds at most two pairs of ( and ), and the pairs are not nested.