Once, Vadim was walking in a field and imagined it as a plane with Cartesian coordinates. There, he saw an infinite number of runes located at points with coordinates (x, y) such that x, y are coprime positive numbers, meaning GCD(x, y) = 1. It goes without saying that their price on the black market is very high, so Vadim decided to use all his strength to collect them.

He had with him a net, which is represented as a convex polygon. Vadim threw it on the ground and then began to collect the runes that fell into it. A rune falls into the net if it is either inside or on the boundary of the thrown net. Vadim doesn’t have time to think, so he asked you to help him count the number of runes in the net.

The first line contains a single integer N — the number of vertices of the polygon describing the thrown net (3 ≤ N ≤ 2 · 10⁵).

In each of the following N lines, two numbers x_i, y_i are given separated by a space — the coordinates of the vertices of this polygon in counterclockwise order (1 ≤ x_i, y_i ≤ 2 · 10⁶). The coordinates are given with exactly three decimal places.

Output the number of runes that fell into the net.

Note that despite the real coordinates of the given polygon, you are required to output an exact value.