Sugar 正在玩他最喜欢的游戏《崩坏：星穹铁道》。他正在游玩一种名为“模拟宇宙”的游戏模式。

游戏的核心玩法是收集名为“祝福”和“奇物”的升级与神器，以增强队伍实力，并完成包含难度逐渐增加的敌人的关卡。

在每次游玩开始时，玩家可以选择一个命途，这将提供命途专属的增益，并增加获得对应命途祝福的概率。在游玩过程中，玩家将完成不同类型的区域（战斗、事件、交易、遭遇、精英、休息），最终目标是到达最后的首领区域并击败首领。

祝福可以通过多种方式积累，为队伍提供各种被动效果和增益。祝福可以通过事件或在休息区域进行强化，以提升其效果。玩家还会获得一种名为“宇宙碎片”的货币，可用于某些随机事件或强化祝福。

Sugar 正在玩低难度模式，因此场景已被大大简化。我们强烈建议你仔细阅读以下内容，特别是对于非常熟悉该游戏的玩家。题目中描述的游戏模式场景与原版游戏有很大不同，请仔细辨别。本次游玩共有 $n$ 个区域，每个区域的类型都是事件。每个区域提供以下两种奖励中的恰好一种：

• 祝福：Sugar 获得一个祝福，他的攻击力立即增加 1。如果 Sugar 拥有至少 1 个宇宙碎片，他可以选择消耗 1 个宇宙碎片来强化该祝福，强化后的祝福可以使他的攻击力增加 2。一个祝福最多只能被强化一次。
• 奇物：Sugar 获得一个奇物。奇物有两种类型，玩家可以从中恰好选择一种。在第 $i$ 个区域获得的第 1 类奇物可以强化不超过 $a_i$ 个在第 $i$ 个区域之前获得的未强化祝福；在第 $i$ 个区域获得的第 2 类奇物可以立即提供 $b_i$ 个宇宙碎片。

注意，宇宙碎片不能用于强化 Sugar 已经获得的祝福。它只能用于强化提供祝福奖励的区域中的祝福，且只能用于强化他在该区域获得的祝福。此外，第 1 类奇物只能强化 Sugar 已经获得的祝福。

Sugar 在本次游玩开始时拥有 0 个祝福、0 个宇宙碎片和 0 点攻击力。请帮他计算在通过 $n$ 个区域后，他能获得的最大攻击力。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^3$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($1 \le n \le 8 \cdot 10^3$)，表示区域的数量。

接下来的 $n$ 行中，第 $i$ 行以一个字符 $t_i$ ($t_i \in \{\text{B}, \text{C}\}$) 开头，表示该区域的奖励类型，即祝福（B）或奇物（C）。如果 $t_i = \text{C}$，则后面跟着两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n$)，表示上述格式的奇物。

保证所有测试用例的 $n$ 之和不超过 $8 \cdot 10^3$。

输出格式

对于每个测试用例，输出一行一个整数，表示 Sugar 在通过 $n$ 个区域后能获得的最大攻击力。

样例

样例输入 1

2
2
B
C 1 1
6
B
B
C 2 1
C 1 2
B
B

样例输出 1

2
8