You are in a large storage facility, with 2^{40} storage locations arranged in a circle.
A truck with a crane on it moves along the circle of storage locations, picking up or putting down crates according to a program. (The truck has an unlimited supply of crates on board, so it can always put more crates down.)
The program consists of 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 there is more than one crate at the current
location, move back to the most recent ( in the sequence of
instructions, and continue the program from there. (This doesn't move
the truck.)
The sample cases contain examples of each of these.
Each storage location begins with one crate, before the crane truck starts running its program.
Mysteriously, if the truck picks up the last crate at a location, another truck instantly comes along and puts down 256 crates there! Similarly, if the truck puts down a crate at a location, and that location then has 257 crates, another truck instantly drives past and picks up 256 of the crates, leaving one behind! So every location always has between 1 and 256 crates.
How many times will the truck move forward or backward before reaching the end of its program?
One line containing an integer T, the number of test cases in the program.
T lines, each containing a crane truck program with up to 2000 characters.
T lines, one for each test case, containing "Case #X: Y" where X is the test case number, and Y is the number of times the truck moves.
1 ≤ T ≤ 20.
1 ≤ the length of the program ≤ 2000.
The program is guaranteed to terminate.
The program will contain at most one pair of ( and ) instructions.
The program will contain at most two pairs of ( and ) instructions.
Input |
Output |
4 ufffdddbbbdd dddd(fdbu)fff dddd(fdddddbu)f(fdddddbu) bf |
Case #1: 6 Case #2: 11 Case #3: 49 Case #4: 2 |
Points | Correct | Attempted |
---|---|---|
8pt | 2 | 3 |
37pt | 0 | 1 |