The Legend of God Flukehn in Eastern

2000ms

262144K

Description:

Flukehn is a well-known god in Eastern and he is invincible with 5 ranks in Go. To challenge the legend of god Flukehn in Eastern, you decided to compose a modified Shogi (the Japanese variant of chess) match with Flukehn.

The chess board can be viewed as an infinite two-dimensional plane. Initially you have $$$n$$$ Pawns uniquely occupying an integral point on the board, and Flukehn has one Gold general occupying an integral point either.

The game is turn-based. At each turn,

you shall pick a Pawn and move it down one unit. More formally, you can move one Pawn with original coordinate $$$(x,y)$$$ to $$$(x,y-1)$$$. Noted that you can't have two Pawns on the same point at any moment.
Then Flukehn shall choose his Gold general to move up, down, left, right, up-left or up-right to the nearest integral point. More formally, with original coordinate $$$(x,y)$$$, Flukehn shall choose his Gold general to move to $$$(x,y+1)$$$, $$$(x,y-1)$$$, $$$(x-1,y)$$$, $$$(x+1,y)$$$, $$$(x-1,y+1)$$$ or $$$(x+1,y+1)$$$.

No one can skip his own turn.

At any moment when Gold general and a Pawn are on the same integral point, the Pawn is considered defeated by Flukehn and should be picked out from the board (Even if it is on your turn).

The initial coordinate of Flukehn's Gold general is on $$$(0,0)$$$.

There is no limitation on turns of the game.

You aim to minimize the number of defeated Pawns while Flukehn aim to maximize it and you both play optimally in the game.

What is final number of Pawns defeated in finite number of turns?

Input:

First line contains one integer $$$T\ (1\le T\le10^6)$$$, denoting the number of test cases.

For every test case, the first line contains one integer $$$n\ (1\le n\le10^6)$$$ as the number of Pawns you initially own.

In the following $$$n$$$ lines, the $$$i^{\text{th}}$$$ line contains two integers $$$x_i,y_i\ (-10^9\le x_i,y_i\le10^9)$$$ as the coordinates of the $$$i^{\text{th}}$$$ Pawn. It is guaranteed that no two Pawns are on the same point and no Pawn is at $$$(0,0)$$$ initially.

The sum of $$$n$$$ for all test cases does not exceed $$$10^6$$$.

Output:

For every test case, output one line containing one integer as the number of Pawns defeated in a finite number of turns.

Sample Input:

Sample Output:

2
2

Note:

In the second example, the third Pawn can continue to move down allowing it to escape from Gold general.

Info

Provider CodeForces Gym

Origin 2021 Jiangxi Provincial Collegiate Programming Contest

Code GYM103366E