Given a bag full of rope segments, you will build the longest loop of rope while alternating colors. The bag contains S segments and each segment will either be blue (B) or red (R). You are required to alternate between colors and because of this requirement you might not use every segment in the bag. If you only have segments of a single color, you will not be able to tie any knots and should output 0. Each segment length is provided in centimeters and each knot in the loop consumes one centimeter of length from the loop. In other words, a knot consumes one-half of a centimeter from of the two segment it connects.

Note that pieces of string that have length 1, if used in making the cycle, might get reduced to just a pair of knots of total length 0. This is allowed, and each such piece counts as having been used.

Input

The first line of input gives the number of cases, N.

N test cases follow. For each test case there will be:

• One line containing the value S, the number of rope segments in the bag.
• One line containing a space separated list of S values. Each value L indicates the segment length in centimeters followed by the letter B or R to indicate the segment color.

Output

For each test case, output one line containing "Case #x: " followed by the maximum length of the rope loop that can be generated with the rope segments provided.

Limits

• 1 ≤ number of rope segments (S) ≤ 1000
• 1 ≤ length of a rope segment (L) ≤ 100

Small Dataset (10 points)

• N ≤ 5

Large Dataset (10 points)

• N ≤ 50

Example

Input

4
1
5B
4
6R 1B 7R 3B
7
5B 4R 3R 2R 5R 4R 3R
2
20B 20R

Output

Case #1: 0
Case #2: 13
Case #3: 8
Case #4: 38