고리 잇기 (작은 문제)

주머니에 밧줄 조각 $S$개가 들어 있다. 각 조각은 파란색(B)이거나 빨간색(R)이고, 길이는 센티미터 단위의 정수로 주어진다. 조각을 매듭으로 이어 닫힌 고리 하나를 만드는데, 고리를 한 바퀴 도는 동안 색이 번갈아 나와야 한다. 이 조건 때문에 주머니의 조각을 모두 쓰지 않아도 된다. 주머니에 한 가지 색만 있으면 매듭을 하나도 묶을 수 없으므로 답은 0이다.

매듭 하나는 고리의 길이를 1센티미터 줄인다. 매듭이 잇는 두 조각에서 0.5센티미터씩 가져가기 때문이다. 조각 $m$개로 만든 고리에는 매듭이 $m$개 있으므로 길이가 모두 $m$센티미터 줄어든다. 가장 작은 고리는 조각 두 개를 매듭 두 개로 이은 것이다.

길이가 1인 조각은 매듭 두 개에 길이를 전부 내주고 0센티미터만 남기기도 한다. 이것도 허용되며, 그런 조각도 사용한 것으로 센다.

만들 수 있는 고리의 최대 길이를 구하라.

첫째 줄에 테스트 케이스의 수 $N$이 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에 조각의 개수 $S$가 주어지고, 둘째 줄에 값 $S$개가 공백으로 구분되어 주어진다. 각 값은 정수 길이 $L$ 바로 뒤에 색을 나타내는 문자 B 또는 R이 붙은 형태다.

제한

• $1 \le N \le 5$
• $1 \le S \le 1000$
• $1 \le L \le 100$

각 테스트 케이스마다 한 줄에 Case #x: y를 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 만들 수 있는 고리의 최대 길이다.