Description

对于一个数列a1,a2......am,其中a1 = 1,am = n , a1 < a2 < ... < am-1 < am 对于每个k(2<=k<=m),ak=ai+aj (1 <= i, j <= k-1),现给定n的值，要求m的最小值.

Format

Input

每行一个数字N，N<=1000

Output

一个数字，代表你的结果

Samples

【输入样例】

4

【输出样例】

3

Limitation

1s, 1024KiB for each test case.