D. Connect the Dotstime limit per test2 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard outputOne 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.InputEach 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$$$.OutputFor each test case, output the number of connected components.ExampleInput310 21 2 42 2 4100 119 2 4100 31 2 57 2 617 2 31Output2
96
61
NoteIn 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$$$.