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