Gạch lát hình thoi

Sau nhiều năm chinh chiến trong lĩnh vực lập trình, Vinko quyết định rẽ hướng sang nghề làm gốm sứ. Ngay trong ngày đầu tiên, anh nhận được một nhiệm vụ vô cùng thử thách: lát sàn một hội trường lớn bằng những viên gạch gốm hình vuông.

Tuy nhiên, thay vì đặt các viên gạch sao cho các cạnh của chúng song song với các bức tường, Vinko lại xoay chúng đi một góc \(45^\circ\), sao cho các đường chéo của viên gạch song song với các cạnh của hội trường. Do đó, hình dạng lát nền sẽ trông như các viên gạch hình thoi được xếp chồng khít nhau.

Sàn của hội trường có dạng hình vuông với kích thước \(10^7 \times 10^7\) (tính theo milimét). Vinko chưa quyết định kích thước cụ thể của các viên gạch, nhưng có một số quy định: \begin itemize

• Tất cả các viên gạch đều là hình vuông, có cùng kích thước.
• Độ dài đường chéo của mỗi viên gạch là một số nguyên dương chẵn
• Viên gạch đầu tiên được đặt sao cho chạm vào tường dưới và tường bên trái.
• Các viên gạch tiếp theo được đặt sao cho cạnh của chúng khớp hoàn toàn với một cạnh của viên gạch đã đặt trước đó.
• Quá trình lát gạch tiếp tục cho đến khi phủ toàn bộ sàn nhà.

\end itemize

\begincenter

Ở hình ví dụ bên trái, điểm có tọa độ \((2,4)\) là điểm trùng với một góc của các viên gạch, nhưng hai điểm còn lại thì không. Tương tự ở hình bên phải có điểm \((4, 3)\) trùng với góc của viên gạch.
\endcenter

Vinko, ngoài tài năng làm gốm, còn là một nhạc sĩ. Anh biết rằng có một số điểm trên sàn hội trường rất quan trọng đối với âm học -- nếu tại một góc của viên gạch trùng với một trong các điểm này thì âm thanh trong hội trường sẽ được cải thiện rõ rệt.

Bạn được cung cấp \(n\) điểm trên mặt sàn (gọi là các điểm âm học). Với mỗi điểm này, hãy xác định có bao nhiêu cách chọn độ dài đường chéo (tức là bao nhiêu kích thước viên gạch hợp lệ) sao cho điểm đó sẽ trùng đúng một góc của viên gạch nào đó khi sàn được lát xong.

Input

\begin itemize

• Dòng đầu tiên chứa một số nguyên \(n\) \((1 \leq n \leq 10^6)\) -- số lượng điểm âm học.

• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) \((0 \leq x_i, y_i \leq 10^7)\) -- tọa độ (theo milimét) của điểm thứ \(i\) tính từ tường bên trái và tường dưới.

Output

• Gồm \(n\) dòng, mỗi dòng in ra số cách chọn độ dài đường chéo (là số nguyên dương chẵn) sao cho điểm tương ứng nằm đúng tại một góc của viên gạch trong phương án lát sàn tương ứng.

Example

3
1 4
0 0
0 9

1
0
3

3
5 1
4 3
2 4

0
1
1

Scoring

• Subtask 1 (25 điểm): \(1 \leq n \leq 10^4\), \(0 \leq x_i, y_i \leq 100\)
• Subtask 2 (45 điểm): \(1 \leq n \leq 10^4\)
• Subtask 3 (30 điểm): Không có ràng buộc bổ sung.