小X有一个1, 2, …, n的序列。当然，n是给定的。Z认为0是一个好数字（看上去很饱满有木有），所以他机智的趁小X不在把这个序列全变成了0（其实只是准备窝）~

可是小X突然回来了！于是Z的计划破灭了。但是他并不甘心，就和小X说：我可以每次从这个序列中选取一些数，然后一起减去一个相同的数（当然也是正整数）。然后经过有(wu)限(qiong)次这样的操作后，这个序列就可以全变成0。

小X当然不信咯，于是Z就求出了他最少要做几次这样的操作，才能使这个序列全部变成0。

一个数字N

输出最少的操作次数

40%数据，n\leq 30

100%数据，n\leq 10^{14}