题目描述

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$ 是上述答案。

3
1 0
1 1
3 2

Case #1: 0
Case #2: 1
Case #3: 3

提示

在样例 $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 完成