D. Connect the Dots
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Example
Input
3
10 2
1 2 4
2 2 4
100 1
19 2 4
100 3
1 2 5
7 2 6
17 2 31
Output
2
96
61
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$$$.