给定一个正整数 $n$。我们希望将 $n$ 表示为尽可能多的正整数之和，要求每个数最多只能使用一次，且不能使用任意两个连续的数。

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 10^{18}$）。

输出格式

你的程序应输出一个整数：满足要求的拆分中最大的加数个数。

样例

输入

6

输出

2