Cycle shifts#27

Cycle shifts

1 second

128 megabytes

Easy

Let us write the integer $n$ in binary notation and generate all its left cyclic shifts, moving the first digit to the end each time.

For example, if $n = 11$ n = 11, in binary this is $1011$ . Its cyclic shifts are $0111$ , $1110$ , $1101$ , $1011$ . The maximum value $m$ among all obtained numbers is $111 0_{2} = 1 4_{10}$ 1110_2 = 14_{10}.

Find the maximum value $m$ that can be obtained from all left cyclic shifts of the binary representation of the given $n$ .

Input

One integer $n$ ( $1 \leq n \leq 2 \cdot 1 0^{9}$ 1 \leq n \leq 2 \cdot 10^9).

Output

One integer $m$ .

Examples

Example 11

Loading

n = 11

111 0_{2} = 1 4_{10}

1 \leq n \leq 2 \cdot 1 0^{9}