After ten years of programming, Vinko has decided to change his profession and
become a ceramist. Already on the first day of his new job he got an extremely
difficult task.
He has to pave the concert hall’s floor with square ceramic tiles. However, he
won’t pave the floor so that the tiles are parallel with the hall’s walls. Instead, he
will rotate them so that the diagonals of the tiles are parallel to the walls.
Vinko has not decided which size of tiles he will use, but he knows they all have to
be the same size, and that the length of their diagonals in millimeters has to be a positive even integer.
He will put the first tile so that it touches the bottom and left walls, and then he will pave the others so
that they share a side with some of the previously set tiles. He will repeat the procedure until he paves
the whole floor, whose dimensions are \(10^{7} \times 10^{7}\) square millimeters.
Besides being a good programmer and ceramist, Vinko is also an excellent musician. Because of that,
he knows that there are \(n\) points on the floor that are crucial for good acoustics in the hall. The hall’s
acoustics would improve significantly if a tile’s corner is at one of the \(n\) points.
The left image shows the paving whose tiles have \(a\) diagonal \(of\) length 4. The point (2, 4) \(at\) \(on\) the corner
\(of\) \(a\) tile, and for \(it\) the acoustics are good, but for the points (4, 3) and (5, 1) are not.
The right image shows the paving whose tiles have \(a\) diagonal \(of\) length 2. The point (4, 3) \(is\) \(at\) the corner
\(of\) \(a\) tile, while points (2, 4) and (5, 1) are not.
Help Vinko determine for each of the \(n\) points in how many ways can he pave the floor (that is, how many
different dimensions of the tiles can he choose) so that the \(i-th\) point is at a tile corner.

Subtask 1 (15 points): \(1 \le n \le 10\,000\), \(0 \le x\)\(i\), y\(i \le 100\)

Subtask 2 (55 points): \(1 \le n \le 10\,000\)

Subtask 3 (40 points): No additional constraints.

The first line contains the integer \(n\) (\(1 \le n \le 10^{6}\)), the number of acoustic points.
The following \(n\) lines contain two integers \(x@@RISE_MATH_BLOCK_0@@i\), y\(i \le 10^{7}\)), which indicates that the \(i-th\) point is
\(x_{i}\) millimeters away from the left wall, and \(y_{i}\) millimeters away from the lower wall of the hall.

In the \(i-th\) of \(n\) lines print the number from the task statement for the \(i-th\) point.

생성자가 기록되지 않았습니다.

출처 COCI 2022/2023 Contest 1