International Programming Contest

April 19, 2003, Blagoevgrad, Bulgaria


Sponsored by STEMO  


Task D. Polygon


A simple polygon with n vertices, (x1, y1), (x2, y2), ..., (xn, yn), is given (2 < n < 104); xi and yi, i = 1, ..., n, are integers within the range: –106 ... 106. The vertices are listed in an order such that the inside area of the polygon is circulated in a clockwise fashion. Write a program D.EXE to find the number of points with integer coordinates lying inside and at the boundary of the polygon.



Your program should read several input data sets. Each set contains the number of vertices on a separated line followed by the pairs of coordinates, separated by a space, each pair on a single line in the standard input. The end of the input is denoted by a digit 0 on a single line.



The result should be written into the standard output, one integer at a line for each input set.


Sample Input


0 0

3 3

4 0

2 1


0 0

0 1

1 1

1 0



Sample Output