给定一袋绳段，你需要用它们制作一个颜色交替的最长绳圈。袋子里有 $S$ 个绳段，每个绳段要么是蓝色（$B$），要么是红色（$R$）。你必须交替使用不同的颜色，由于这个要求，你可能无法使用袋子里的所有绳段。如果你只有一种颜色的绳段，你将无法打任何结，此时应输出 0。每个绳段的长度以厘米为单位给出，绳圈中的每个结会消耗绳圈 $1$ 厘米的长度。换句话说，一个结会消耗它所连接的两根绳段各 $0.5$ 厘米的长度。

注意，长度为 $1$ 的绳段如果用于制作绳圈，可能会缩减为仅有两个结且总长度为 $0$。这是允许的，并且每个这样的绳段都算作已被使用。

输入格式

第一行输入包含测试用例的数量 $N$。

接下来是 $N$ 个测试用例。对于每个测试用例：

• 第一行包含一个整数 $S$，表示袋中绳段的数量。
• 第二行包含一个由空格分隔的 $S$ 个值的列表。每个值 $L$ 表示绳段的长度（以厘米为单位），后面紧跟字母 $B$ 或 $R$ 表示绳段的颜色。

输出格式

对于每个测试用例，输出一行，格式为 "Case #$x$: "，后跟使用所提供的绳段可以生成的绳圈的最大长度。

数据范围

• $1 \le$ 绳段数量 ($S$) $\le 1000$
• $1 \le$ 绳段长度 ($L$) $\le 100$

小数据 (10 分)

• $N \le 5$

大数据 (10 分)

• $N \le 50$

样例

输入样例 1

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

输出样例 1

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