Sherlock and Parentheses (Small)

Sherlock and Watson are taking a computer programming course together. Today the tutor covered balanced parentheses. 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 (T), where T is a balanced string.
• S has the form T1T2, where T1 and T2 are both balanced strings.

Sherlock finished his solution in a couple of minutes and started bragging about it, so Watson gave him another task. Build a string S of L + R characters that contains exactly L left parentheses ( and exactly R right parentheses ), and make the number of balanced non-empty substrings of S as large as possible. Two substrings count as different whenever they start at different positions or end at different positions, even if they spell the same text. S itself does not have to be balanced.

Sherlock claims he can build the string himself once he knows that maximum. Find the maximum possible number of balanced non-empty substrings.

The first line contains the number of test cases T. Each of the next T lines contains two integers L and R.

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 described above.

• $1 \le T \le 100$
• $0 \le L \le 20$
• $0 \le R \le 20$
• $1 \le L + R \le 20$

In the first test case of the sample, ( is the only string you can build, and it has no balanced non-empty substring.

In the second test case, () is optimal, and its only balanced substring is the whole string.

In the third test case, both ()()( and (()() are optimal. For ()()(, the balanced substrings are () from position 1 to position 2, () from position 3 to position 4, and ()() from position 1 to position 4.