最近，你饱受可怕噩梦的折磨。在这些梦中，一群愤怒的 Fenwick 蜜蜂在有着重枝和轻枝的树周围追赶你。你讨厌被它们摆弄的刺蜇到。因此，你决定在三天前制作一个捕梦网，但制作过程很棘手，你无法弄清楚细节。

规划你的捕梦网变得如此压力山大，以至于你过去三个晚上都失眠了，一直在思考长长的毛线、卡米歇尔数（Carmichael numbers）和几何。目前唯一的进展是一些令人费解的图纸（见图 D.1）以及一个观察：跨越半径为 $r$ 的圆上 $\theta$ 度的弦长为 $2r \cdot \sin(\theta/2)$。但这能有什么帮助呢？你宁愿再次梦见 Fenwick 蜜蜂，也不愿再多受一天这个可怕项目的折磨。你现在就需要解决这个问题！

图 D.1：一个有 8 个刻口的捕梦网，展示了两种用毛线缠绕它的方法。左边的捕梦网每条弦跨越 2 个刻口，而右边的捕梦网每条弦跨越 3 个刻口。

为了制作一个捕梦网，你取一个有 $n$ 个均匀分布刻口的轮子，刻口从 $1$ 到 $n$ 编号。你将一根毛线缠绕在这个轮子上，每条弦跨越 $k$ 个刻口：从刻口 1 开始，你重复地将毛线连接到向前 $k$ 个刻口处，直到再次回到刻口 1。例如，当 $n = 8$ 且 $k = 3$ 时，你将依次经过刻口 1, 4, 7, 2, 5, 8, 3, 6, 1。

捕梦网的效果取决于所用毛线的总量。你需要选择每条弦跨越的刻口数 $k$，使得毛线的总长度最大。答案与捕梦网的半径无关。

输入格式

输入包含：

• 一行，包含一个整数 $n$ ($3 \le n \le 10^9$)，表示轮子上的刻口数量。

输出格式

输出一个整数 $k$ ($1 \le k < n$)，表示在每条弦跨越 $k$ 个刻口时，能使所用毛线总长度最大的 $k$。

如果有多个可行解，你可以输出其中任意一个。

样例

输入样例 1

8

输出样例 1

3

输入样例 2

5

输出样例 2

2

输入样例 3

6

输出样例 3

5