Problem: codeforces/2020D
Time limit: 2000 ms, Memory limit: 256 MB

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 Format

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 Format

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


Sample Input 1

```
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
```

Sample Output 1

```
2
96
61
```

Notes

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 $ .