Description

你打过棒球吗？Lua学姐的社团希望举办⼀场特殊赛制的棒球赛，准备邀请你做这场⽐赛的记分员。 学姐告诉你，你需要按照不同的操作进⾏相应的记录：

整数x：本回合得分x，记录该得分。 “+”：本回合得分是前两次有效得分之和，记录该得分。 “D”：本回合得分是上⼀次有效得分的两倍，记录该得分。 “C”：扣除上⼀次有效得分，并移除上次有效得分记录。

保证记录“+”、“D”、“C”操作时，前⾯总是存在有效的分数，答案都在int范围内。

Input Format

输⼊包含多组数据，第⼀⾏⼀个正整数T，表示输⼊数据的组数。

每组输⼊数据包含两⾏，第⼀⾏⼀个正整数n，表示操作的个数；第⼆⾏为n个字符，为具体的操作。

Output Format

每组输⼊数据输出⼀个正整数，为最终得分。

2
5
5 2 C D +
8
5 -2 4 C D 9 + +​

30
27​

Hint

输入数据的解释：

样例1:

5 2 C D +

解释：

"5" - 记录加 5 ，记录现在是 [5]

"2" - 记录加 2 ，记录现在是 [5, 2]

"C" - 使前⼀次得分的记录⽆效并将其移除，记录现在是 [5].

"D" - 记录加 2 * 5 = 10 ，记录现在是 [5, 10]. "+" - 记录加 5 + 10 = 15 ，记录现在是 [5, 10, 15].

所有得分的总和 5 + 10 + 15 = 30

样例2：

5 -2 4 C D 9 + +

解释：

"5" - 记录加 5 ，记录现在是 [5]

"-2" - 记录加 -2 ，记录现在是 [5, -2]

"4" - 记录加 4 ，记录现在是 [5, -2, 4]

"C" - 使前⼀次得分的记录⽆效并将其移除，记录现在是 [5, -2]

"D" - 记录加 2 * -2 = -4 ，记录现在是 [5, -2, -4]

"9" - 记录加 9 ，记录现在是 [5, -2, -4, 9]

"+" - 记录加 -4 + 9 = 5 ，记录现在是 [5, -2, -4, 9, 5]

"+" - 记录加 9 + 5 = 14 ，记录现在是 [5, -2, -4, 9, 5, 14]

所有得分的总和 5 + -2 + -4 + 9 + 5 + 14 = 27