Problem Description

In the first quadrant of the Cartesian coordinate system, there is a rectangular region with bottom-left corner at $(0,0)$ and top-right corner at $(10^{100},10^{100})$. Inside the region there are a positive even number of integer lattice points. You need to find a polyline inside the region that starts from $(0,0)$ and ends at $(10^{100},10^{100})$ such that:

• Each segment of the polyline is parallel to the $x$-axis or the $y$-axis.
• The polyline must not pass through any of the given lattice points.
• The polyline divides the whole region into two parts, and the two parts contain the same number of given lattice points.
• The polyline has as few turning points as possible.

It can be proven that such a polyline always exists. You only need to output the number of turning points of a polyline that satisfies the constraints.

Note that the coordinates of turning points do not have to be integers.

Input Format

The first line contains a positive integer $T$, the number of test cases.

For each test case, the first line contains a positive even integer $n$, the number of given lattice points.

Then follow $n$ lines. The $i$-th line contains two positive integers $x_i, y_i$, meaning the $i$-th given lattice point is at $(x_i, y_i)$.

Output Format

Output $T$ lines. Each line contains a positive integer, the number of turning points of a polyline satisfying the constraints.

3
4
1 1
1 2
4 1
4 2
6
1 2
1 3
2 1
2 2
2 3
3 2
12
1 3
2 2
2 3
2 4
3 1
3 2
3 4
3 5
4 2
4 3
4 4
5 3

2
3
4

Hint

Sample Explanation

For the first test case, one valid polyline is: $(0,0) \to (2.5,0) \to (2.5,10^{100}) \to (10^{100},10^{100})$. It has two turning points: $(2.5,0)$ and $(2.5,10^{100})$.

Constraints

For all test cases, $1 \leq T \leq 10^4$, $1 \leq \sum n \leq 5 \times 10^5$, $1 \leq x_i, y_i \leq n$. It is guaranteed that $n$ is a positive even number, and within each test case, no two lattice points have the same coordinates.

Translated by ChatGPT 5