Sherlock and Parentheses (Small)

Time limit5sMemory limit512 MB

Summary

Given L left and R right parentheses, arrange all of them to maximize the count of balanced non-empty substrings, counted by position.

Level: Medium5 of 10
Topics: Greedy, Math, Combinatorics, Brute force
Solved: No attempts yet

Problem

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.

Input

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

Output

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.

Constraints

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

Hint

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.

Examples2

Example 1

Input

Expected output

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

Example 2
Input
```
1
0 1
```
Expected output
```
Case #1: 0
```