Points Strictly Inside

Statement

A simple polygon has n corners with integer coordinates, listed in order around its boundary. Count the lattice points (points with integer coordinates) that lie strictly inside it. Points on the boundary do not count.

Input

The first line has n. Each of the next n lines has the coordinates x y of one corner, in order around the boundary.

Output

Print one integer: the number of lattice points strictly inside the polygon.

Constraints

3 <= n <= 200000
|x|, |y| <= 10^9
The answer is below 4 x 10^18, so it fits in a signed 64-bit integer. Hint: the area and the boundary points together determine the interior count.

Example 1

4
0 0
4 0
4 4
0 4

9

The interior points are (1,1) to (3,3): a 3 by 3 block of nine points.

Example 2

3
0 0
4 0
0 3

3

The strictly interior points are (1,1), (2,1) and (1,2). The points on the three edges do not count.