Ингрид держит многоугольный магазин в далекой стране. Она продает только выпуклые многоугольники с целыми координатами. Ее клиенты предпочитают многоугольники, которые можно правильно разрезать на две половины, то есть разрез должен быть прямым с начальной и конечной точками в вершинах многоугольника, а обе половины должны быть непустыми и иметь целочисленную площадь. Чем больше способов правильно разрезать многоугольник - тем он дороже.

Например, имеется три способа разрезать левый многоугольник правильным образом и два способа - правый многоугольник.

Многоугольники в магазине всегда отличного качества, поэтому бизнес расширяется. Теперь Ингрид нужен какой-то автоматический инструмент, чтобы определить количество способов правильного разрезания многоугольника. Это очень важно для ее магазина, иначе Вы потратите много времени на установление цен - только представьте, сколько времени потребуется, чтобы установить цену на фургон среднего размера с многоугольниками. Не могли бы Вы помочь Ингрид и написать для нее программу?

Входные данные

В первой строке записано целое число n (4 ≤ n ≤ 200 000) - количество вершин многоугольника. Каждая из следующих n строк содержит координаты вершин: пару целых чисел xi и yi (-109 ≤ xi, yi ≤ 109) в строке.

Указанный многоугольник выпуклый, а его вершины указаны в порядке обхода.

Выходные данные

Выведите одно целое число w - количество способов разрезать многоугольник правильным образом.