As part of his preparation for algorithmic competitions, Bajtek decided to learn something about concurrent programming. After all, even in the Potyczki Algorytmiczne, distributed tasks have appeared before.

Bajtek started by writing $n$ very simple programs. All programs share one global integer variable $x$, and additionally, each of them possesses one private counter $y$. Each program consists of a sequence of operations, and each operation is of one of the following four types:

• $W$ – read the value of the global variable $x$ into the private counter $y$,
• $Z$ – write the value of the private counter $y$ to the global variable $x$,
• $+ c$ – increase the private counter $y$ by a positive constant $c$,
• $- c$ – decrease the private counter $y$ by a positive constant $c$.

Bajtek ran all the programs in parallel. The initial values of all counters $y$ and the variable $x$ were $0$. The programs were executed in a certain interleaving, meaning all operations from all programs were executed one after another, in some order satisfying the condition that at any moment, a prefix of each program had been executed.

This interleaving turned out to be quite unfortunate, and the final value of the variable $x$ was so small that it surprised Bajtek. He even suspects that it is not possible and his computer cheated him. Help Bajtek verify his concerns and write a verifier that, for the given programs, calculates what the minimum possible value of the variable $x$ is after the parallel execution of all programs.

Input

The first line of input contains a single integer $t$ ($1 \le t \le 100\,000$) denoting the number of test cases.

The description of each test case begins with a line containing an integer $n$ ($1 \le n \le 100\,000$) denoting the number of programs written by Bajtek. The next $2n$ lines contain descriptions of the individual programs. The description of each program consists of two lines. The first one contains a single integer $\ell$ ($1 \le \ell \le 1\,000\,000$) denoting the number of operations in the given program. The second contains a sequence of $\ell$ operations, each of which is of one of the four types:

• a single letter $W$ – denoting a read operation,
• a single letter $Z$ – denoting a write operation,
• the sign $+$ and an integer $c$ ($1 \le c \le 10^9$) – denoting an operation of increasing the counter by a constant $c$,
• the sign $-$ and an integer $c$ ($1 \le c \le 10^9$) – denoting an operation of decreasing the counter by a constant $c$.

The sum of all values $\ell$ across all programs in all test cases will not exceed $1\,000\,000$.

Output

Output $t$ lines; the $i$-th of them should contain a single integer denoting the minimum possible value of $x$ after the parallel execution of the programs from the $i$-th test case.

Examples

Input 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

Output 1

5
7

Note

The example explanation shows a valid interleaving for the first test case that results in the minimum final value of $x = 5$.