Однажды Вадим гулял по полю и представлял его в виде плоскости с декартовыми координатами. Тут он увидел бесконечное количество рун, которые лежали в точках с координатами (x, y) такими, что x, y — натуральные взаимно простые числа, то есть НОД(x, y) = 1. Не нужно объяснять, что их цена на чёрном рынке очень высока, поэтому Вадим решил использовать все свои силы, чтобы собрать их.

С собой у него была сеть, которая представляет из себя выпуклый многоугольник. Вадим кинул её на землю, после чего начал собирать попавшие в неё руны. Руна попадает в сеть, если она оказывается либо внутри, либо на границе выкинутой сети. Времени думать у Вадима нет, поэтому он попросил вас помочь ему посчитать количество рун в сети.

В первой строке дано единственное число N — количество вершин многоугольника, описывающего кинутую сеть (3 ≤ N ≤ 2 · 10⁵).

В каждой из следующих N строк через пробел даны по два числа x_i, y_i — координаты вершин этого многоугольника в порядке обхода против часовой стрелки (1 ≤ x_i, y_i ≤ 2 · 10⁶). Координаты даны ровно с тремя знаками после запятой.

Выведите количество рун, попавших в сеть.

Заметьте, что, несмотря на вещественные координаты данного многоугольника, от вас требуется вывести точное значение.