你管理着一座城市。你的城市中将会建立若干所工厂，并且会有若干名工人来到你的城市寻找工作。你需要合理安排各项事务，以最大化总利润。

每所工厂都有一个生产能力 $x_i$，这意味着在单轮生产中：

• 如果有一名工人在其中工作，它将产生 $x_i$ 的利润。
• 如果没有工人在其中工作，它将不产生利润。
• 每所工厂最多只能有一名工人工作。

你已经预见到在接下来的 $n$ 天里，每天都会发生以下两种事件之一：

• 一名工人来寻找工作。在这名工人到达后，你可以重新分配所有工人的位置（包括当前已在工厂中工作的工人）。具体来说，对于每名工人，你可以安排他/她去任意工厂工作，或者让他/她保持空闲。
• 一所生产能力为 $x_i$ 的工厂建立。在这所工厂建立后，如果有空闲的工人，你可以选择是否安排一名空闲的工人去这所工厂工作。当然，你也可以让这所工厂保持空置。特别地，如果没有空闲的工人，这所工厂只能保持空置。

在当天的事件执行完毕后，所有工厂将进行一轮生产，并根据上述规则产生利润。

你需要求出最大总利润。

输入格式

输入包含多组测试数据。输入的第一行包含一个整数 $T$ ($1 \le T \le 10^6$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$)，表示天数。

接下来的 $n$ 行中，第 $i$ 行首先包含一个字符 $op_i$ ($op_i \in \{\text{W}, \text{F}\}$)，表示第 $i$ 天的事件类型。如果 $op_i = \text{W}$，表示当天有一名工人来寻找工作；否则，如果 $op_i = \text{F}$，则后面紧跟一个整数 $x_i$ ($1 \le x_i \le 10^7$)，表示当天建立了一所生产能力为 $x_i$ 的工厂。

保证所有测试数据的 $n$ 之和不超过 $10^6$。

输出格式

对于每组测试数据，输出一行包含一个整数，表示最大总利润。

样例

输入样例 1

2
8
F 1
F 2
W
F 100
W
W
F 10000
W
9
W
F 51
F 1
F 1
F 1
F 1
F 100
F 100
W

输出样例 1

20509
557

说明

我们对第一组样例数据解释如下：

总利润为 $0 + 0 + 0 + 100 + 102 + 102 + 10102 + 10103 = 20509$。