题目描述

设无向图 $G = (V, E)$。将顶点集合 $V$ 划分为两个子集 $S$ 和 $V \setminus S$，定义割 $(S, V \setminus S)$ 的大小为所有一端属于 $S$、另一端属于 $V \setminus S$ 的边的数量。

在所有可能的划分中，割的最小值称为该图的全局最小割大小。

当图只有一个孤立点时，全局最小割大小为 $0$。

给定正整数 $n$，如下生成一个 $n-2$ 个点（编号 $3\cdots n$）的无向图：

• $u,v$ 间有边当且仅当 $u\nmid v$ 且 $v\nmid u$。

求无向图的全局最小割大小。

输入格式

一行一个正整数 $n\ (3\le n\le 10^{14})$。

输出格式

一行一个整数表示答案。

5

2

20

12

82508002

55005333

提示

样例 1 解释

当 $n=5$ 时，对应的图如下：

一种划分方法是 $S=\{3\},V\setminus S=\{4,5\}$，此时图中两条红色边满足一段属于 $S$、另一端属于 $V \setminus S$，故割的大小为 $2$。

可以证明不存在其他划分方法能使得割的大小更小，所以该图的全局最小割大小为 $2$。