One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist.

To play the game, Alice draws a straight line and marks $n$ points on it, indexed from $1$ to $n$. Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs $m$ operations of the following type:

• She picks three integers $a_i$, $d_i$ ($1 \le d_i \le 10$), and $k_i$.
• She selects points $a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i$ and connects each pair of these points with arcs.

After performing all $m$ operations, she wants to know the number of connected components$^\dagger$ these points form. Please help her find this number.

$^\dagger$ Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^5$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 2 \cdot 10^5$).

The $i$-th of the following $m$ lines contains three integers $a_i$, $d_i$, and $k_i$ ($1 \le a_i \le a_i + k_i\cdot d_i \le n$, $1 \le d_i \le 10$, $0 \le k_i \le n$).

It is guaranteed that both the sum of $n$ and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.

Output

For each test case, output the number of connected components.

Note

In the first test case, there are $n = 10$ points. The first operation joins the points $1$, $3$, $5$, $7$, and $9$. The second operation joins the points $2$, $4$, $6$, $8$, and $10$. There are thus two connected components: $\{1, 3, 5, 7, 9\}$ and $\{2, 4, 6, 8, 10\}$.

In the second test case, there are $n = 100$ points. The only operation joins the points $19$, $21$, $23$, $25$, and $27$. Now all of them form a single connected component of size $5$. The other $95$ points form single-point connected components. Thus, the answer is $1 + 95 = 96$.

In the third test case, there are $n = 100$ points. After the operations, all odd points from $1$ to $79$ will be in one connected component of size $40$. The other $60$ points form single-point connected components. Thus, the answer is $1 + 60 = 61$.