一个美好的夜晚,爱丽丝坐下来玩经典游戏“连点成线”,但有一个转折。
为了玩游戏,Alice 画一条直线并在其上标记 $$$n$$$ 点,索引从 $$$1$$$ 到 $$$n$$$。最初,点之间没有弧,因此它们都是不相交的。之后,Alice 执行以下类型的 $$$m$$$ 操作:
- 她选择了三个整数 $$$a_i$$$、$$$d_i$$$ ($$$1 \le d_i \le 10$$$) 和 $$$k_i$$$。
- 她选择点 $$$a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i$$$ 并用弧连接每对这些点。
执行完所有 $$$m$$$ 操作后,她想知道这些点形成的连通分量 $$$^\dagger$$$ 的数量。请帮她找到这个号码。
$$$^\dagger$$$ 如果两个点之间存在通过多个(可能为零)弧和其他点的路径,则称两个点位于一个连通分量中。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^5$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 2 \cdot 10^5$$$)。
以下 $$$m$$$ 行中的第 $$$i$$$ 包含三个整数 $$$a_i$$$、$$$d_i$$$ 和 $$$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$$$)。
保证所有测试用例的 $$$n$$$ 总和和 $$$m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出连接组件的数量。
示例
输入 #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
输出 #1
2 96 61
注意
在第一个测试用例中,有 $$$n = 10$$$ 点。第一个操作连接点 $$$1$$$、$$$3$$$、$$$5$$$、$$$7$$$ 和 $$$9$$$。第二个操作连接点 $$$2$$$、$$$4$$$、$$$6$$$、$$$8$$$ 和 $$$10$$$。因此有两个连通分量:$$$\{1, 3, 5, 7, 9\}$$$ 和 $$$\{2, 4, 6, 8, 10\}$$$。
在第二个测试用例中,有 $$$n = 100$$$ 点。唯一的操作连接点 $$$19$$$、$$$21$$$、$$$23$$$、$$$25$$$ 和 $$$27$$$。现在它们全部形成一个大小为 $$$5$$$ 的单个连接组件。其他 $$$95$$$ 点形成单点连接组件。因此,答案是$$$1 + 95 = 96$$$。
在第三个测试用例中,有 $$$n = 100$$$ 点。操作完成后,从 $$$1$$$ 到 $$$79$$$ 的所有奇数点都将位于大小为 $$$40$$$ 的一个连通分量中。其他 $$$60$$$ 点形成单点连接组件。因此,答案是 $$$1 + 60 = 61$$$。