Поликарп очень любит играть в игру сапёр. Недавно он нашёл похожую игру и там такие правила.
На поле находятся мины, для каждой известны координаты её местоположения (\(x_i, y_i\)). Каждая мина имеет время жизни в секундах, после которого она взорвётся. После взрыва мина также детонирует все мины по вертикали и горизонтали на расстоянии \(k\) (две перпендикулярные линии). В итоге получаем взрыв на поле в виде символа «плюс» ('+'). Таким образом, один взрыв может вызвать новые взрывы, а новые взрывы — следующие и так далее.
Также Поликарп может сам взорвать одну любую мину в каждую секунду, начиная с нулевой. После этого также проходит цепная реакция взрывов. Мины взрываются моментально и также моментально детонируют другие мины по написанным выше правилам.
Поликарп хочет установить новый рекорд и просит вас помочь ему рассчитать, за какое минимальное количество секунд можно взорвать все мины.
Выходные данные
Выведите \(t\) строк, каждая из строк должна содержать ответ на соответствующий набор входных данных — минимальное количество секунд, за которое можно взорвать все мины.
Примечание
Первый набор входных данных примера. Первый пример:
- Секунда \(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)\) и на поле не остаётся мин.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|