There are $N$ possible locations where a hidden spaceship may be located, numbered from $1$ to $N$. Your task is to find its exact location.

You are provided with a function int spaceship(int M), known as the Spaceship Operator. It compares your guess M with the spaceship's true location and returns an integer:

• -1 if the spaceship is at a smaller location than M.
• 1 if the spaceship is at a larger location than M.
• 0 if M is the spaceship's location.

Implement the function int locate(int N), which should return the location of the spaceship.

Input

The grader provides a single integer $N$, the number of possible locations.

Output

Your function should return the location of the spaceship as an integer.

Constraints

• $1 \le N \le 10^9$
• The spaceship is located at exactly one position between $1$ and $N$, inclusive.

Scoring

For each test case, let:

• $X$ be the minimum number of calls to spaceship(int M) required to guarantee finding the spaceship's location for any hidden position between $1$ and $N$.
• $Y$ be the number of calls to spaceship(int M) made by your solution.

If your solution reports an incorrect location, the score for that test case is 0. Otherwise, the score is computed as follows:

• If $Y \le X$, the score is 100.
• Otherwise, the score is $\max\left(0,\ 100 - 10^{\,Y-X}\right)$.

The score for a submission is the minimum score obtained over all test cases.

Sample Grader

The sample grader reads two integers: $N$ and $L$, representing the number of possible locations and the position of the spaceship respectively.

If int locate(int N) successfully locates the spaceship, Correct is printed, followed by the number of calls to int spaceship(int M).

Otherwise, Contestant answer does not match jury answer is printed, followed by the contestant's and jury's answer.