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

Вера — для смертных
— Mountain of Faith

Санаэ смотрит на звёзды, находясь на горе. Для неё вера — это место, где встречаются ветры и расходятся пути, и точка, в которой сходятся все направления. Во славу всего святого, давайте вместе проследим знак веры.

Даны $$$n$$$ различных целочисленных точек на плоскости, где $$$i$$$-я точка находится в $$$(x_i,y_i)$$$. Чтобы раскрасить точки, выберите два целых числа $$$k_1$$$ и $$$k_2$$$ так, чтобы каждая из четырёх областей, на которые плоскость разбивается прямыми $$$x=k_1+0.5$$$ и $$$y=k_2+0.5$$$, содержала хотя бы одну точку. Каждая точка $$$(x,y)$$$ окрашивается в зависимости от области, в которой она лежит:

  • Верхняя левая ($$$x\leq k_1$$$ и $$$y \gt k_2$$$): точка окрашивается в красный цвет.
  • Верхняя правая ($$$x \gt k_1$$$ и $$$y \gt k_2$$$): точка окрашивается в зелёный цвет.
  • Нижняя левая ($$$x\leq k_1$$$ и $$$y\leq k_2$$$): точка окрашивается в синий цвет.
  • Нижняя правая ($$$x \gt k_1$$$ и $$$y\leq k_2$$$): точка окрашивается в жёлтый цвет.
Допустимая раскраска третьего набора входных данных, где $$$k_1=4$$$ и $$$k_2=5$$$.

Найдите количество различных раскрасок. Две раскраски считаются различными тогда и только тогда, когда существует хотя бы одна точка, окрашенная по-разному, независимо от выбора $$$k_1$$$ и $$$k_2$$$.

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

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

В первой строке каждого набора входных данных дано целое число $$$n$$$ ($$$4 \leq n \leq 2 \cdot 10^6$$$).

В следующих $$$n$$$ строках даны по два целых числа $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$), задающие координаты $$$i$$$-й точки.

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

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

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

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

Пример
Входные данные
5
4
1 1
2 2
3 3
4 4
4
1 4
4 1
1 1
4 4
8
7 2
5 7
2 7
1 3
6 7
3 6
7 5
1 6
8
6 1
3 6
1 4
1 1
4 2
5 5
3 4
4 1
6
5 5
5 4
3 5
1 5
5 3
2 2
Выходные данные
0
1
12
8
4
Примечание

В первом наборе входных данных не существует допустимого креста.

Во втором наборе входных данных выбор $$$x = y = 2$$$ даёт допустимую раскраску. Можно доказать, что эта раскраска единственна.

В третьем наборе входных данных допустимая раскраска показана в условии.