104035 - 截铁丝

现有长度为total的铁丝,要将之截成n小段(n>2),每段的长度不小于1,如果其中任意三小段铁丝都不能拼成三角形,则n的最大值为多少?

Input

输入一个整数total(5<total<150 000 000)。

Output

输出一个整数n。

Examples

Input

144

Output

10
Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题