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

Note

输入数据的解释： 
样例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​