Polygon in the plane is defined by integer coordinates of its n vertices in the Cartesian coordinate system. Find the number of points with integer coordinates lying inside a polygon (not on the border). The polygon sides do not touch (with the exception of the neighboring - in the vertices) and do not intersect.

Input

The first line contains the number n (3 ≤ n ≤ 10000). The following n lines contain a pair of integers - the coordinates of the points (that do not exceed 1000000 by absolute value). If you connect the points in this manner, and join the first and last point, you obtain the polygon.

Output

Print the number of points with integer coordinates lying strictly inside a polygon.