eolymp
bolt
Try our new interface for solving problems
Problems

The boundary of the polygon

The boundary of the polygon

Time limit 2 seconds
Memory limit 64 MiB

Polygon in the plane defined by integer coordinates of its N vertices in the Cartesian coordinate system. Required to find the number of points with integer coordinates lying on the boundary of the polygon. The sides of each other not in contact (with the exception of the neighboring - in the tops) and do not intersect.

Input data

The first line contains the number N, the following N lines - a pair of numbers - the coordinates of points. If you connect the dots in this manner, and join the first and last point, we obtain the polygon. 3N100000, the coordinates of the vertices of the whole and do not exceed 1,000,000,000.

Output data

Derive a single number - the number of points with integer coordinates on the boundary of the polygon.

Examples

Input example #1
3
10 0
0 10
0 0
Output example #1
30