Description

你现在处于一个巨大的仓库中，仓库有 $2^{40}$ 个储存位置，这些位置以环形排列。

一辆带有起重机的卡车沿着这些储存位置的环形轨道移动，根据一段程序来搬运箱子（卡车上有无限数量的箱子，因此可以随时放下更多箱子）。

程序由以下指令序列组成：

• b：向后移动一个位置
• f：向前移动一个位置
• u：在当前位置取走一个箱子
• d：在当前位置放下一个箱子
• (：什么都不做
• )：如果当前位置的箱子数量大于 1，则回到指令序列中最近的 ( 处，并从那里继续执行程序（卡车不会移动）。

程序中的 ( 和 ) 指令总是成对出现：一个 ( 之后总会有一个匹配的 )。程序中最多只会有两对这样的括号，并且如果有两对括号，它们不会嵌套——也就是说，可能有以下三种情况：

• 程序中没有 ( 或 ) 指令；
• 程序中有一个 (，之后有一个匹配的 )；
• 程序中有一个 (，之后有一个 )，再之后有另一个 (，最后还有一个 )。

样例中包含了每种情况的例子。

在起重机卡车开始执行程序前，每个储存位置初始都有一个箱子。

神奇的是，如果卡车在某个位置取走了最后一个箱子，另一辆卡车会立刻过来并在该位置放下 256 个箱子！同样地，如果卡车在某个位置放下一个箱子，导致该位置箱子数达到 257，另一辆卡车会立刻过来取走 256 个箱子，只留下一个！因此，每个位置的箱子数始终保持在 1 到 256 之间。

卡车在到达程序末尾前，前进或后退了多少次？

Input Format

第一行包含一个整数 $T$，表示测试用例的数量。

接下来的 $T$ 行，每行包含一条起重机卡车的程序，长度不超过 2000 个字符。

Output Format

共 $T$ 行，每行输出 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号，$Y$ 是卡车移动的次数。

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

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

Hint

限制条件

• $1 \leq T \leq 20$。
• 程序长度 $1 \leq \text{length} \leq 2000$。
• 保证程序一定会终止。

小数据集

• 时间限制：5 秒。
• 程序中最多只会有一对括号指令。

大数据集

• 时间限制：10 秒。
• 程序中最多只会有两对括号指令。

由 ChatGPT 4.1 翻译