P16580 [GKS 2016 #B] Sherlock and Parentheses

Sherlock 和 Watson 最近参加了一门计算机编程课程。今天，老师向他们讲解了括号匹配问题。一个仅由字符 ( 和 ) 组成的字符串 $S$ 是**平衡的**，如果它满足： - 它是空字符串，或者： - 它具有 $(S)$ 的形式，其中 $S$ 是平衡字符串，或者： - 它具有 $S_1 S_2$ 的形式，其中 $S_1$ 是平衡字符串且 $S_2$ 是平衡字符串。 Sherlock 很快就写好了解法，并开始吹嘘自己有多厉害，于是 Watson 给他出了一个题来考验他的能力。Watson 要求 Sherlock 生成长度为 $L + R$ 的字符串 $S$，其中总共有 $L$ 个左括号 ( 和 $R$ 个右括号 )。此外，该字符串必须包含尽可能多的**不同**的非空平衡子串。（只要两个子串在原串中的起始和结束下标不同，就视为不同，即使它们的内容完全相同）。注意 $S$ 本身不一定是平衡的。 Sherlock 确信，一旦他知道非空平衡子串的最大可能数量，他就能解决这个问题。你能帮他找出这个最大数量吗？

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。每个测试用例由一行两个整数 $L$ 和 $R$ 组成。

对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是上述答案。

在样例 $1$ 中，唯一可能的字符串是 `(`。没有非空的平衡子串。 在样例 $2$ 中，最优字符串是 `()`。只有一个非空平衡子串：整个字符串本身。 在样例 $3$ 中，字符串 `()()` 和 `(()()` 都能给出相同的最优答案。 例如，对于 `()()(`，三个平衡子串分别是：下标 $1$ 到 $2$ 的 `()`，下标 $3$ 到 $4$ 的 `()`，以及下标 $1$ 到 $4$ 的 `()()`。 ### 限制条件 $1 \le T \le 100$。 **小数据集（测试集 1 – 可见）** $0 \le L \le 20$。 $0 \le R \le 20$。 $1 \le L + R \le 20$。 **大数据集（测试集 2 – 隐藏）** $0 \le L \le 10^5$。 $0 \le R \le 10^5$。 $1 \le L + R \le 10^5$。 翻译由 DeepSeek V4 Pro 完成