测试数据来自 system/1558

描述

延绵的山(mountain)

在Prascles世界里,有一座绵延的山,有10^1000个山峰.每个山峰的高度不尽相同.经地理学家和数学家研究发现,这座山的山峰高度符合下面的规律:
1.如果把若干个(包括一个)相邻山峰的高度序列看作一个片段的话,就没有两个相邻的片段是完全相同的,如1,2,1,2是不允许的.
2.在满足条件1的前提下,每个山峰高度取最小正整数.
3.满足编号小的山峰高度最小总是比满足编号大的山峰高度最小优先.如前4个山峰的高度为1,2,1,3而不是1,2,3,1.
事实上,从1号山峰开始,各山峰的高度分别为
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,...
但是这么多山峰,10^1000个耶,列出所有山峰的高度是不可能的.现在Prascles世界的人就聘请高级程序师----你来帮助他们,已知山峰编号,求它的高度.

格式

输入格式

只有一行,为山峰编号m.(1<=m<=10^1000)
输入数据没有前导零和多余的空格.

输出格式

只有一行,为山峰高度h.

样例1

样例输入1

20

样例输出1

3

限制

所有数据时限一秒。

来源

本人的原创题 ^_^