Acoustic Corner Tiles

Vinko is tiling a concert hall floor of size $10^7 \times 10^7$ square millimeters with identical square tiles. However, he has an unusual constraint: instead of aligning the edges of the tiles with the walls, he rotates them so that their diagonals (of length d) are parallel to the walls. Moreover, d must be a positive even integer.

The tiling begins with the first tile placed so that one of its corners touches both the left and back walls. Every subsequent tile is added so that it shares an entire side with at least one tile already placed, until the floor is completely covered. Because the tiles are rotated by 45°, each tile has vertices which, when computed in the coordinate system of the hall, are not simply all lattice points; rather, only certain points become tile corners.

Vinko, who is also a gifted musician, has identified n critical points in the hall that can greatly improve the acoustics if a tile corner exactly falls on one of them. Precisely, for a given tile diagonal length d, a point (x, y) is a tile corner if and only if the following conditions hold:

• Divisibility condition: d divides both 2x and 2y (i.e. the numbers \(\frac{2x}{d}\) and \(\frac{2y}{d}\) are integers).
• Parity condition: \[ \frac{2x}{d} + \frac{2y}{d} \equiv 1 \pmod{2}. \]

Your task is: for each of the given n points, determine the number of valid tile sizes (i.e. the number of positive even integers d) such that when the floor is tiled with tiles of diagonal d, the corresponding point becomes a tile corner.

Note: The tiling pattern is uniquely determined by the process described above.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), the number of critical points. Each of the following n lines contains two integers x and y (0 ≤ x, y ≤ 10⁷), representing a point in millimeters.

You may assume that the floor dimensions guarantee that the tiling covers the entire area.

outputFormat

Output n lines. The i-th line should contain a single integer indicating the number of valid even tile diagonal lengths d for which the i-th point is exactly a tile corner.

sample

3
2 4
4 3
5 1

1
1
0