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 ≤ 10
18).
Output
Write to the output the minimum twisting generator of the number
n.
Example(s)
sample input | sample output |
6
|
5
|
