为了准备算法竞赛，Bajtek 决定学习一些关于并发编程的知识。毕竟，即使在 Potyczki Algorytmiczne 中也曾出现过分布式任务。

Bajtek 从编写 $n$ 个非常简单的程序开始。所有程序共享一个全局整数变量 $x$，此外每个程序都有一个私有计数器 $y$。每个程序由一系列操作组成，每种操作属于以下四种类型之一：

• W – 将全局变量 $x$ 的值读取到私有计数器 $y$ 中，
• Z – 将私有计数器 $y$ 的值写入全局变量 $x$，
• + c – 将私有计数器 $y$ 增加一个正整数常量 $c$，
• - c – 将私有计数器 $y$ 减少一个正整数常量 $c$。

Bajtek 并行运行了所有程序。所有计数器 $y$ 和变量 $x$ 的初始值均为 $0$。程序以某种交错方式执行，即所有程序中的所有操作按某种顺序一个接一个地执行，且满足在任何时刻都已执行了每个程序的一个前缀。

这种交错执行的结果非常不理想，最终变量 $x$ 的值小到让 Bajtek 非常惊讶。他甚至怀疑这是否可能，并认为他的计算机欺骗了他。请帮助 Bajtek 验证他的担忧，并编写一个验证器，计算在所有程序并行执行后，变量 $x$ 可能达到的最小值。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 100\,000$)，表示测试用例的数量。

每个测试用例的描述以一行包含整数 $n$ ($1 \le n \le 100\,000$) 开始，表示 Bajtek 编写的程序数量。接下来的 $2n$ 行包含各个程序的描述。每个程序的描述由两行组成。第一行包含一个整数 $\ell$ ($1 \le \ell \le 1\,000\,000$)，表示该程序中的操作数量。第二行包含 $\ell$ 个操作，每个操作属于以下四种类型之一：

• 单个字母 W – 表示读取操作，
• 单个字母 Z – 表示写入操作，
• 字符 + 和一个整数 $c$ ($1 \le c \le 10^9$) – 表示将计数器增加常量 $c$ 的操作，
• 字符 - 和一个整数 $c$ ($1 \le c \le 10^9$) – 表示将计数器减少常量 $c$ 的操作。

所有测试用例中所有程序的所有 $\ell$ 值之和不超过 $1\,000\,000$。

输出格式

输出 $t$ 行；第 $i$ 行应包含一个整数，表示第 $i$ 个测试用例中程序并行执行后 $x$ 可能达到的最小值。

样例

输入 1

2
2
12
W + 2 Z W + 2 Z W + 2 Z W + 2 Z
12
W + 3 Z W + 3 Z W + 3 Z W + 3 Z
3
3
W W - 5
5
+ 9 Z + 1 Z W
8
+ 10 Z - 2 Z - 5 W - 1 Z

输出 1

5
7

说明 1

在第一个测试用例中，以下交错执行方式可以得到最小的最终 $x$ 值：

程序 1: W + 2 Z W + 2 Z W + 2 Z W + 2 Z
程序 2: W + 3 Z W + 3 Z W + 3 Z W + 3 Z

y1: 0 0 0 0 0 0 2 2 2 2 2 2 2 2 4 4 4 6 6 6 6 8 8 8
y2: 0 3 3 3 3 6 6 6 6 9 9 9 9 2 2 2 2 2 5 5 5 5 5 5
x : 0 0 0 3 3 3 3 6 6 6 9 2 2 2 2 4 4 4 4 6 6 6 8 5