Little L has been studying Kleene three-valued logic.

In three-valued logic, the value of a variable can be: True (abbreviated as $T$), False (abbreviated as $F$), or Unknown (abbreviated as $U$).

Logical operations can also be defined in three-valued logic. Since Little L is a slow learner, he has only mastered the logical NOT operation $\neg$, which follows these rules: $\neg T = F, \neg F = T, \neg U = U$.

Now, Little L has $n$ three-valued logic variables $x_1, \dots, x_n$. Little L wants to perform some interesting experiments, so he has written down $m$ statements. The statements are of the following three types, where $\leftarrow$ denotes assignment: 1. $x_i \leftarrow v$, where $v$ is one of $T, F, U$; 2. $x_i \leftarrow x_j$; 3. $x_i \leftarrow \neg x_j$.

Initially, Little L assigns an initial value to each variable, and then executes these $m$ statements in order.

Little L hopes that after executing all the statements, the final value of every variable is equal to its initial value. Under this condition, Little L wants to minimize the number of variables whose initial value is $U$.

In this problem, you need to help Little L find an initial assignment scheme that minimizes the number of $U$ variables, such that after executing all statements, the final value of every variable is equal to its initial value. Little L guarantees that for all test cases in this problem, such an initial assignment scheme is guaranteed to exist.

Input

The input is read from the file tribool.in.

The test cases contain multiple sets of test data. The first line of the input contains two integers $c$ and $t$, representing the test case number and the number of test data sets, respectively. For the samples, $c$ indicates that the sample shares the same constraints as test case $c$.

Next, for each test data set: The first line contains two integers $n$ and $m$, representing the number of variables and the number of statements, respectively. The next $m$ lines provide each statement in the order of execution. The first character $v$ describes the type of the statement. It is guaranteed that $v$ is one of $T, F, U, +, -$. If $v$ is one of $T, F, U$, the next part is an integer $i$, representing the statement $x_i \leftarrow v$. If $v$ is $+$, the next part is two integers $i, j$, representing the statement $x_i \leftarrow x_j$. If $v$ is $-$, the next part is two integers $i, j$, representing the statement $x_i \leftarrow \neg x_j$.

Output

Output to the file tribool.out.

For each test data set, output a single integer on a new line, representing the minimum number of $U$ variables among all valid initial assignment schemes.

Examples

Input 1

1 3
3 3
- 2 1
- 3 2
+ 1 3
3 3
- 2 1
- 3 2
- 1 3
2 2
T 2
U 2

Output 1

0
3
1

Note

In the first test data set, the $m$ statements are: $x_2 \leftarrow \neg x_1$; $x_3 \leftarrow \neg x_2$; * $x_1 \leftarrow x_3$.

A valid initial assignment scheme is $x_1 = T, x_2 = F, x_3 = T$, which has $0$ $U$ variables. Since there is no assignment scheme with fewer than $0$ $U$ variables, the output is $0$.

In the second test data set, the $m$ statements are: $x_2 \leftarrow \neg x_1$; $x_3 \leftarrow \neg x_2$; * $x_1 \leftarrow \neg x_3$.

The only valid assignment scheme is $x_1 = x_2 = x_3 = U$, which has $3$ $U$ variables, so the output is $3$.

In the third test data set, the $m$ statements are: $x_2 \leftarrow T$; $x_2 \leftarrow U$;

An initial assignment scheme that minimizes the number of $U$ variables is $x_1 = T, x_2 = U$. $x_1 = x_2 = U$ is also a valid scheme, but it does not minimize the number of $U$ variables.

Input 2

See tribool/tribool2.in in the contestant directory.

Output 2

See tribool/tribool2.ans in the contestant directory.

Note

This sample satisfies the conditions for test case 2.

Input 3

See tribool/tribool3.in in the contestant directory.

Output 3

See tribool/tribool3.ans in the contestant directory.

Note

This sample satisfies the conditions for test case 5.

Input 4

See tribool/tribool4.in in the contestant directory.

Output 4

See tribool/tribool4.ans in the contestant directory.

Note

This sample satisfies the conditions for test case 8.

Constraints

For all test data, it is guaranteed that: $1 \le t \le 6$, $1 \le n, m \le 10^5$; For each operation, $v$ is one of $T, F, U, +, -$, and $1 \le i, j \le n$.