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)~ is on the corner of a tile, and for it the acoustics are good, but for the points ~(4, 3)~ and ~(5, 1)~ they 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.

Input Specification

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_i, y_i~ ~(0 \le x_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.

Output Specification

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

Constraints

Subtask	Points	Constraints
~1~	~15~	~1 \le n \le 10\,000~, ~0 \le x_i, y_i \le 100~
~2~	~55~	~1 \le n \le 10\,000~
~3~	~40~	No additional constraints.

Sample Input 1

3
1 4
0 0
0 9

Sample Output 1

1
0
3

Sample Input 2

3
5 1
4 3
2 4

Sample Output 2

0
1
1

Explanation for Sample Output 2

Images from the task statement correspond to the second example.