셜록과 괄호 (작은 버전)

셜록과 왓슨은 프로그래밍 수업을 함께 듣고 있다. 오늘 수업에서는 짝이 맞는 괄호 문자열을 다뤘다. 문자 (와 )로만 이루어진 문자열 S가 짝이 맞는다는 것은 다음 중 하나가 성립한다는 뜻이다.

• S가 빈 문자열이다.
• S가 (T) 꼴이고, T가 짝이 맞는 문자열이다.
• S가 T1T2 꼴이고, T1과 T2가 모두 짝이 맞는 문자열이다.

셜록이 풀이를 금방 짜 놓고 자랑하자 왓슨이 다른 문제를 냈다. 왼쪽 괄호 (가 정확히 L개, 오른쪽 괄호 )가 정확히 R개인 길이 L + R짜리 문자열 S를 만들되, 짝이 맞으면서 비어 있지 않은 부분 문자열의 개수를 최대로 하라는 것이다. 두 부분 문자열은 내용이 같더라도 시작 위치나 끝 위치가 다르면 서로 다른 것으로 센다. S 자체가 짝이 맞는 문자열일 필요는 없다.

셜록은 그 최댓값만 알면 문자열을 직접 만들어 낼 수 있다고 장담한다. 짝이 맞으면서 비어 있지 않은 부분 문자열 개수의 최댓값을 구하라.

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

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 위에서 구한 최댓값이다.

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

예제의 첫 번째 테스트 케이스에서 만들 수 있는 문자열은 ( 하나뿐이고, 짝이 맞으면서 비어 있지 않은 부분 문자열은 없다.

두 번째 테스트 케이스에서는 ()가 최적이며, 짝이 맞는 부분 문자열은 문자열 전체 하나뿐이다.

세 번째 테스트 케이스에서는 ()()(와 (()()가 모두 최적이다. ()()(의 경우 짝이 맞는 부분 문자열은 1번째부터 2번째 문자까지의 (), 3번째부터 4번째 문자까지의 (), 1번째부터 4번째 문자까지의 ()()이다.