Sherlock과 괄호

Sherlock과 Watson은 최근 컴퓨터 프로그래밍 강좌에 등록했다. 오늘 강사는 이들에게 올바른 괄호 문제를 가르쳤다. 문자 ( 및/또는 )로만 이루어진 문자열 S은 다음 조건을 만족하면 올바른 문자열이다:

• 빈 문자열이거나,

• (S) 형태이며, 이때 S가 올바른 문자열이거나,

• $S_{1}$ $S_{2}$ 형태이며, 이때 $S_{1}$가 올바른 문자열이고 $S_{2}$도 올바른 문자열이다.

Sherlock은 매우 빠르게 풀이를 작성하고 자신이 얼마나 뛰어난지 자랑하기 시작했다. 그래서 Watson은 그의 지식을 시험하기 위해 문제를 하나 냈다. Watson은 Sherlock에게 L + R개의 문자로 이루어지고, 왼쪽 괄호 (가 모두 L개이며 오른쪽 괄호 )가 모두 R개인 문자열 S를 만들라고 했다. 또한 이 문자열은 서로 다른, 비어 있지 않은 올바른 부분 문자열을 가능한 한 많이 가져야 한다. (두 부분 문자열의 내용이 우연히 같더라도 문자열에서 시작하거나 끝나는 인덱스가 다르면 서로 다른 것으로 간주한다.) S 자체는 올바른 문자열일 필요가 없음에 유의하라.

Sherlock은 비어 있지 않은 올바른 부분 문자열의 가능한 최대 개수를 알게 되면 이 문제를 풀 수 있다고 확신한다. 그 최댓값을 찾도록 도와줄 수 있는가?

제한

1 ≤ T ≤ 100. 시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

0 ≤ L ≤ 20. 0 ≤ R ≤ 20. 1 ≤ L + R ≤ 20.

큰 데이터 세트 (테스트 세트 2 - 비공개)

0 ≤ L ≤ $10^{5}$. 0 ≤ R ≤ $10^{5}$. 1 ≤ L + R ≤ $10^{5}$.

입력의 첫째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 두 정수 L과 R이 주어지는 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 위에서 설명한 정답이다.

케이스 1에서 가능한 유일한 문자열은 (이다. 비어 있지 않은 올바른 부분 문자열은 없다. 케이스 2에서 최적의 문자열은 ()이다. 비어 있지 않은 올바른 부분 문자열은 문자열 전체인 하나뿐이다. 케이스 3에서는 두 문자열 ()()(와 (()()가 동일한 최적의 답을 낸다. 예를 들어 케이스 ()()(에서 올바른 세 부분 문자열은 인덱스 1부터 2까지의 (), 인덱스 3부터 4까지의 (), 그리고 인덱스 1부터 4까지의 ()()이다.