Description

小A带着一个金连环去住宾馆。 金边环的结构如下： 1：其长度为N，正好等于他在宾馆住的天数。

2：金连环上的N个金环，呈一个链形，环环相扣。

小A要给宾馆老板一个金环做为住宿的费用，但小A不想把金环一个个全拆下来。 于是他发现当N=7时 他只要解开第三个金环，于是整个金连环会变成三个部分 长度分别为2，1，4。

于是他就可以完成住宿7天时的支付工作。

但当小A要住宿8天时，则对于一个长度为8的金连环无法在只解开一个金环的前提下，完成8天的支付工作。

现在给出N，问至少要断开几个金环

Format

Input

一行给出数字N

N<=1e15

Output

如题

Samples

8

2

1000

7