Stone Game with Doubling Moves

There are n stones on the table. Two players, Mirko and Slavko, play according to the following rules:

• Mirko makes the first move, then Slavko, then Mirko, and so on.
• In his first move, Mirko may remove any positive number of stones (at most n).
• In every subsequent move, a player must take at least 1 stone and at most 2 times the number of stones taken in the previous move. In any move the number of stones taken cannot exceed the number of stones remaining.
• The player who takes the last stone wins.

Assuming both players play optimally, determine the minimum number of stones that Mirko must take in his first move in order to guarantee a win. In other words, find the smallest positive integer k (with 1 ≤ k ≤ n) such that if Mirko takes k stones on his first move, he can force a win no matter how Slavko plays.

Note: In subsequent moves the maximum number of stones a player can take is given by \(\min(2\times k, r)\), where \(k\) is the number of stones taken in the previous move and \(r\) is the number of stones remaining.

inputFormat

The input consists of a single integer n (n ≥ 1) representing the total number of stones.

Input Format:

n

outputFormat

Output the minimum number of stones Mirko must take in his first move in order to guarantee a win under optimal play.

Output Format:

answer

sample

1

1