CUTSTICK - Cut Stick

no tags 

Ann meets another problem.

Since she has a n-meter-long stick, she wants to cut it into small ones. Of course she would not let the small sticks be shorter than 1 meter. At the same time she is so mean that she can't stand that any three of the small sticks could make a triangle. That is to say, any 3 of the small sticks can not form a triangle if there are 3 or more small sticks.

You can assume that the small sticks only have integer length.

Input

A line contains a positive integer n, which is the length of the long stick. It does not exceed 10^5.

Output

Print a number -- the maximum number of small sticks Ann could get.

Example

Input:
1
2
3
4

Output:
1
2
2
3

hide comments
kokonut_hustle: 2020-11-24 18:42:42

there are many test cases per input, so you have to read all the input and output for all test cases

Stanislav Zholnin: 2016-05-13 00:04:36

It is not obvious that there are several test cases per input.


Added by:[UNI]Jonathans
Date:2013-03-16
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:TJU 2012 Team Selection