Bạn có biết rằng, cực từ Bắc không cố định tại một vị trí địa lý mà luôn dịch chuyển? Chuyện này tuy không liên quan lắm đến bạn, nhưng nó lại là rắc rối to lớn cho các nhà khoa học đang nghiên cứu tại cực Bắc.

Chuyện rằng, những la bàn tại các trạm nghiên cứu nơi đây đã cũ và chỉ có thể vận hành chính xác nếu các trục chính của nó nằm cùng hướng với cực từ. Những trục chính của nó bao gồm 4 hướng Đông - Tây - Nam - Bắc cùng 4 hướng phụ tạo thành góc ~45^\texttt{o}~ với 4 hướng chính. Với việc từ trường ngày càng thay đổi nhanh chóng vì biến đổi khí hậu, càng ngày càng nhiều trạm nghiên cứu sẽ không thể sử dụng la bàn được nữa.

Để có thể lường trước được tình hình này, các nhà nghiên cứu cần phải tính trước số trạm có nguy cơ hỏng trong ~N~ trạm đang vận hành tại đây. Giả sử rằng cực từ luôn rơi vào toạ độ của một trạm nghiên cứu, với mỗi điểm rơi hãy tính số trạm vẫn có thể vận hành được la bàn (bao gồm cả trạm tại cực từ).

Input

• Dòng đầu tiên gồm số nguyên dương ~N~ (~1 \leq N \leq 10^5~) duy nhất là số lượng trạm nghiên cứu.
• ~N~ dòng tiếp theo, dòng thứ ~i~ ghi 2 số nguyên ~x_i~ và ~y_i~ (~-10^9 \leq x_i, y_i \leq 10^9~) là toạ độ của trạm nghiên cứu thứ ~i~.

Output

Ghi ra ~N~ số nguyên, mỗi số nguyên là số lượng trạm nghiên cứu vẫn hoạt động được nếu cực từ nằm ở đó.

Sample input

5
5 7
6 9
8 7
8 11
4 5

Sample output

2 3 4 3 1

Subtask

• ~30\%~ số test có ~1 \leq N \leq 1000~.
• ~70\%~ số test còn lại không có điều kiện gì thêm.