The boundary of the polygon

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

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. 3 ≤ N ≤ 100000, the coordinates of the vertices of the whole and do not exceed 1,000,000,000.

Output

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

Examples