На декартовой плоскости $$$n$$$ различных точек покрашено в черный цвет, а все остальные точки покрашены в белый. Каждая черная точка имеет целые координаты.
Также есть робот, который может за одну команду переместиться на единицу в любом из направлений 'U' (вверх), 'D' (вниз), 'L' (влево) или 'R' (вправо).
Путь робота из точки $$$p_{1}$$$ в точку $$$p_{2}$$$ это последовательность команд робота, такая, что если робот, который находится в точке $$$p_{1}$$$, выполнит эту последовательность, то окажется в точке $$$p_{2}$$$.
Кратчайший путь робота из точки $$$p_{1}$$$ в точку $$$p_{2}$$$ это путь, последовательность которого состоит из минимально возможного количества команд.
Необходимо посчитать количество пар точек $$$p_i$$$, $$$p_j$$$ ($$$i \neq j$$$), таких что для этой пары точек выполняется условие:
Все точки с целочисленными координатами на любом кратчайшем пути робота из точки $$$p_{i}$$$ в точку $$$p_{j}$$$ покрашены в черный цвет.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — количество точек, покрашенных в черный цвет.
Следующие $$$n$$$ строк каждого набора входных данных содержат по два целых числа $$$x_{i}, y_{i}$$$ ($$$-10^{9} \le x_{i}, y_{i} \le 10^{9}$$$) — координаты точки $$$p_{i}$$$. Все точки попарно различны.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^{5}$$$.
Для каждого набора входных данных выведите одно целое число — ответ на задачу.
350 01 00 11 12 0180 0-1 0-2 00 -1-1 -10 11 10 21 22 21 36 -25 -25 -36 -34 -33 -35 -43-100 100-101 99-99 101
16 70 0
В первом тестовом случае $$$16$$$ подходящих пар точек:
| Kotlin Heroes: Episode 13 |
|---|
| Закончено |
