CF2228D.Sanae, Cross and Color

Faith Is for the Transient People

— Mountain of Faith

Upon the mountain, Sanae gazes at the stars. Faith, for her, is where winds encounter one another and choices diverge, and it is the point where all directions meet. For the glory of the Holy Cross, let us trace the sign of faith together.

There are $n$ distinct integer points in the plane, where the $i$-th point is located at $(x_i,y_i)$. To color the points, choose two integers $k_1$ and $k_2$ such that each of the four regions divided by the lines $x=k_1+0.5$ and $y=k_2+0.5$ contains at least one point. Each point $(x,y)$ is colored according to the region it lies in:

• Top-left ($x\leq k_1$ and $y \gt k_2$): the point is colored red.
• Top-right ($x \gt k_1$ and $y \gt k_2$): the point is colored green.
• Bottom-left ($x\leq k_1$ and $y\leq k_2$): the point is colored blue.
• Bottom-right ($x \gt k_1$ and $y\leq k_2$): the point is colored yellow.

A valid coloring of the third test case, where $k_1=4$ and $k_2=5$.

Find the number of distinct colorings, where two colorings are considered distinct if and only if there exists at least one point colored differently, regardless of the choice of $k_1$ and $k_2$.

信仰属于 transient 之人

——《信仰之山》

在山巅，早苗凝望着星辰。对她而言，信仰是风与风相遇之处，是选择分岔之处，亦是所有方向交汇之点。为圣十字架的荣光，让我们一同描绘信仰的印记。

平面上有 $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$ 的具体取值）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($4 \leq n \leq 2 \cdot 10^6$).

The following $n$ lines each contain two integers $x_i$, $y_i$ ($1 \leq x_i, y_i \leq n$), representing the coordinates of the $i$-th point.

It is guaranteed that the points are pairwise distinct in each test case.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, output the number of distinct colorings.

对于每个测试用例，输出不同染色方案的数量。

In the first test case, no valid cross exists.

In the second test case, choosing $x = y = 2$ yields a valid coloring. It can be proved that this coloring is unique.

In the third test case, a valid coloring is shown in the legend.

在第一个测试用例中，不存在有效的十字形。

在第二个测试用例中，选择 $x = y = 2$ 可得到一种有效的染色方案。可以证明该染色方案是唯一的。

在第三个测试用例中，图例中展示了一种有效的染色方案。