#P1950. 蛋蛋的问题(三)

蛋蛋的问题(三)

这学期到了十一周了,蛋蛋突然要去金工实习了,想到要拿着锉刀,钳子,锯子什么的做锤子了,头就有点大了,因为它挺好玩的,但是,也是很累的,看着学弟坐在机房悠闲地敲着代码,蛋蛋学长决定要让他们好好忙忙,这道题就是为了你们而出的,学弟们,加油!!

问题很简单,只是需要动手就够了,要求是,给你n米长的钢筋,钢筋大家都知道吧,就是一根钢条,目的很简单,让你自己动手把这一根很长的钢筋切成M段,保证他们中的任意三段都不能构成三角形,听起来会感觉乱乱的,其实我要的答案很简单,就是你能把这根钢筋截成多少条,条数要最多,还有就是长度不能少于1米。

简单吧,大家抓紧时间AC吧。

Input

有多组数据,每组数据只有一行,一行里面只有一个数N(4<=N<=1000000);

Output

输出占一行,对应每个N输出最多的条数M

Sample Input

7
144

Sample Output

4
10

HINT

Source