Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

D. Соедини точки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Одним уютным вечером Алиса решила сыграть в классическую игру «Соедини точки», но с подвохом.

Чтобы начать игру, Алиса рисует прямую линию и отмечает на ней $$$n$$$ точек, проиндексированных числами от $$$1$$$ до $$$n$$$. Изначально между точками нет рёбер, так что все они попарно не соединены. Затем Алиса выполняет $$$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$$$ Алиса соединяет ребром каждую пару из них.

Алиса хочет узнать, сколько компонент связности$$$^\dagger$$$ образуют эти точки после выполнения всех $$$m$$$ операций.

$$$^\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$$$).

В $$$i$$$-й из следующих $$$m$$$ строк содержится три целых числа $$$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$$$ каждая.

Выходные данные

Для каждого набора входных данных выведите количество компонент связности.

Пример
Входные данные
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
Выходные данные
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$$$.