A polygon (not necessarily convex) on a plane is given by the coordinates of its vertices. It is required to count the number of points with integer coordinates lying inside it (but not on its border).
Input data format
The first line contains N (3 ≤N ≤1000) – the number of vertices of the polygon. The next N lines contain the coordinates (X
i, Y
i) of the polygon vertices in clockwise order. Xi and Yi are integers, modulo not exceeding 1000000.
Output data format
Output a single number – desired number of points.
Examples
| # |
Input |
Output |
| 1 |
4
-1 -1
-1 1
1 1
1-1 |
1 |
| 2 |
3
0 0
0 2
20
|
0 |