P8858 Polyline.

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.

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 $T$ lines. Each line contains a positive integer, the number of turning points of a polyline satisfying the constraints.

#### 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 | Test Point ID | $n \leq$ | Special Constraint | |:-------------:|:--------:|:------------------:| | $1 \sim 2$ | $4$ | None. | | $3 \sim 4$ | $10$ | None. | | $5 \sim 6$ | $50$ | None. | | $7 \sim 8$ | $10^5$ | The answer is guaranteed to be no more than $3$. | | $9 \sim 10$ | $10^5$ | None. | 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