Cho đa giác \(n\) đỉnh với tọa độ nguyên. Hãy đếm số điểm nguyên nằm trên biên của đa giác (bao gồm các đỉnh).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(n\) (\(3 \le n \le 10^5\)).
• \(n\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x_i, y_i\) (\(|x_i|, |y_i| \le 10^6\)).

Định dạng đầu ra

• Một số nguyên duy nhất là số điểm nguyên trên biên.

Ví dụ

Input:

3
0 0
6 0
3 4

Output:

9

Ràng buộc

• 40% số điểm: \(n \le 1000\).
• 60% số điểm còn lại: không có ràng buộc gì thêm.