Sherlock and Parentheses (Large)

Sherlock and Watson learned about balanced parenthesis strings in a programming class. A string $S$ made only of the characters ( and ) is balanced when one of the following holds.

• $S$ is the empty string.
• $S$ has the form ($A$), where $A$ is a balanced string.
• $S$ has the form $AB$, where $A$ and $B$ are both balanced strings.

Sherlock solved the exercise at once and bragged about it, so Watson gave him another problem. Build a string $S$ of length $L + R$ that contains exactly $L$ opening parentheses ( and exactly $R$ closing parentheses ), and make the number of non-empty balanced substrings as large as possible. Two substrings count as different when they start at different indexes or end at different indexes, even if their contents are the same. $S$ itself does not have to be balanced.

Sherlock says that once he knows the maximum, he can build the string himself. Given $L$ and $R$, find the maximum possible number of non-empty balanced substrings.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $L$ and $R$ separated by a space.

For each test case, print one line in the form Case #x: y, where x is the test case number starting from 1 and y is the maximum you found.

• $1 \le T \le 100$
• $0 \le L \le 10^5$
• $0 \le R \le 10^5$
• $1 \le L + R \le 10^5$

For $L = 1$ and $R = 0$, the only possible string is (, and it has no non-empty balanced substring.

For $L = 1$ and $R = 1$, the string () is optimal, and the whole string is the single balanced substring.

For $L = 3$ and $R = 2$, both ()()( and (()() reach the maximum of 3. In ()()(, for example, the balanced substrings are () from index 1 to 2, () from index 3 to 4, and ()() from index 1 to 4.