G. Необычный сапёр
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп очень любит играть в игру сапёр. Недавно он нашёл похожую игру и там такие правила.

На поле находятся мины, для каждой известны координаты её местоположения ($$$x_i, y_i$$$). Каждая мина имеет время жизни в секундах, после которого она взорвётся. После взрыва мина также детонирует все мины по вертикали и горизонтали на расстоянии $$$k$$$ (две перпендикулярные линии). В итоге получаем взрыв на поле в виде символа «плюс» ('+'). Таким образом, один взрыв может вызвать новые взрывы, а новые взрывы — следующие и так далее.

Также Поликарп может сам взорвать одну любую мину в каждую секунду, начиная с нулевой. После этого также проходит цепная реакция взрывов. Мины взрываются моментально и также моментально детонируют другие мины по написанным выше правилам.

Поликарп хочет установить новый рекорд и просит вас помочь ему рассчитать, за какое минимальное количество секунд можно взорвать все мины.

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

В первой строке входных данных записано целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных в тесте.

Перед каждым набором в тесте записана пустая строка.

Далее идёт строка, которая содержит целые числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^9$$$) — количество мин и расстояние, которое задевают мины при взрыве, соответственно.

Затем следуют $$$n$$$ строк, $$$i$$$-я из которых описывает $$$x$$$ и $$$y$$$ координаты $$$i$$$-й мины и время до её взрыва ($$$-10^9 \le x, y \le 10^9$$$, $$$0 \le timer \le 10^9$$$). Гарантируется, что все мины имеют различные координаты.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^5$$$.

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

Выведите $$$t$$$ строк, каждая из строк должна содержать ответ на соответствующий набор входных данных — минимальное количество секунд, за которое можно взорвать все мины.

Пример
Входные данные
3

5 0
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

5 2
0 0 1
0 1 4
1 0 2
1 1 3
2 2 9

6 1
1 -1 3
0 -1 9
0 1 7
-1 0 1
-1 1 9
-1 -1 7
Выходные данные
2
1
0
Примечание
Первый набор входных данных примера.

Первый пример:

  • Секунда $$$0$$$: взрываем мину в клетке $$$(2, 2)$$$ она никого не задевает так как $$$k=0$$$.
  • Секунда $$$1$$$: взрываем мину в клетке $$$(0, 1)$$$, а мина в клетке $$$(0, 0)$$$ взрывается сама.
  • Секунда $$$2$$$: взрываем мину в клетке $$$(1, 1)$$$, а мина в клетке $$$(1, 0)$$$ взрывается сама.

Второй пример:

  • Секунда $$$0$$$: взрываем мину в клетке $$$(2, 2)$$$ получаем:
  • Секунда $$$1$$$: взрывается мина в клетке $$$(0, 0)$$$ и так как $$$k=2$$$ взрыв задевает мины в клетках $$$(0, 1)$$$ и $$$(1, 0)$$$, а их взрывы задевают мину в клетке $$$(1, 1)$$$ и на поле не остаётся мин.