348. Twisting the Number

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Professor Dull invented a direction in number theory. This is the theory of "twisting generators". Consider a positive integer number p. Let it contain b bits (the highest bit should be 1). Consider all possible b cycle shifts of the binary notation of the number p. Let's make a set from all this shifts and call it W(p). Note, some of the shifts can start with zero. Let's say that the number p twistingly generates the set W(p). For example, W(11) = {7, 11, 13, 14}.

The number p is called a twisting generator of the number n, if the union of all sets W(1), W(2),..., W(p) contains {1, 2,..., n} as a subset. Your task is to find the minimum generator of the given number n.

Input
The first line of the input contains the integer number n (1 ≤ n ≤ 1018).

Output
Write to the output the minimum twisting generator of the number n.

Example(s)
sample input
 
sample output
 
6

5