Ingrid 在一个遥远的国家经营着一家多边形商店。她只出售顶点坐标为整数的凸多边形。 她的顾客更喜欢那些能以“恰当方式”切割成两半的多边形，即切割线必须是直线，且起点和终点都在多边形的顶点上，同时切割出的两部分都必须是非空的，且面积为整数。切割多边形的“恰当方式”越多，该多边形就越昂贵。

例如，左侧的多边形有三种恰当的切割方式，右侧的多边形有两种。

商店里的多边形质量总是极好的，因此业务正在不断扩大。现在，Ingrid 需要一个自动工具来确定切割多边形的恰当方式的数量。这对她的商店非常重要，否则她将花费大量时间来定价——试想一下，为一辆中型货车的多边形定价需要花费多少时间。你能帮 Ingrid 编写这个工具吗？

输入格式

输入的第一行包含一个整数 $n$ —— 多边形的顶点数 ($4 \le n \le 200\,000$)。 接下来的 $n$ 行，每行包含一对整数 $x_i$ 和 $y_i$，表示顶点的坐标 ($-10^9 \le x_i, y_i \le 10^9$)。 给定的多边形是凸多边形，且顶点按遍历顺序给出。

输出格式

输出一个整数 $w$ —— 切割多边形的恰当方式的数量。

样例

样例输入 1

5
7 3
3 5
1 4
2 1
5 0

样例输出 1

3

样例输入 2

4
1 1
3 1
5 5
1 3

样例输出 2

2