Consider a hidden vector V with n integer numbers in strictly increasing order. Given an integer x that belongs to V, you will play a game to guess the position j where V[j] = x. You have to use a “black box” B, with parameters x and a position i inside V. If there is a j ∈ {i − 1, i, i + 1 } such that V[j] = x, you win the game. Otherwise, B will tell you whether x < V[i−1] or x > V[i+1].

Given n, what is the minimum number of calls to B to win the game?

Input

Input consists of several cases, each one with an n between 1 and 10^{18}.

Output

For every n, print the worst-case number of calls to B to win the game, assuming a strategy that minimizes that worst-case cost.

Public test cases

**Input**

1 2 4 9 10 1000000000000000

**Output**

1 1 2 2 3 49

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++