Define number game (between Alice and Bob) as follows: they agree on a positive number $n$, then Alice will pick a number $x$ from $1$ to $n$. Each time, Bob will select some intervals and ask Alice whether $x$ is in any of the intervals. To be clear, it's a yes/no question. One special rule about this game is that, Alice can lie once (more precisely at most once).

We're in the middle of the Game. Given $n$, all questions already been asked by Bob and the answers by Alice respectively. Please compute the minimum number of additional questions that Bob needs to ask to uniquely determine the value of $x$.

Input

There are at most $10000$ test cases. Each case consists of $n$ and $m$ (the number of questions always been asked by Bob), separated by a space. For the following $m$ lines, the first number is $c$, then the line is followed by $c$ pairs $[s_i, t_i]$ ($1 \leq s_i \leq t_i \leq n$, $1 \leq i \leq c$) denoting the $i$-th interval in this question, then a string "yes" or "no" denoting the answer. You may assume that Alice is strictly obeying the rule and it's always possible to find the answer $x$ if Bob continues to play the game.

$1 \leq n \leq 10^{16}$, $0 \leq m \leq 10$, and $1 \leq c \leq 100$

Output

For each test case, print a single line containing one integer — the minimum number of additional questions required.

Example

Input

1 0
2 0
2 2
1 1 1 yes
1 1 1 no
2 2
1 1 1 yes
1 1 1 yes
2 3
1 1 1 yes
1 1 1 no
1 1 1 yes

Output

0
3
1
0
0