Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Tidy Bits

Limits 1s, 512 MB

Read an integer variable, and determine the smallest positive integer that has the same number of 1s in its bit representation as the number you read.

The following numbers all have the same number of 1s in their bit representation: 7 (111), 13 (1101), 37 (100101), etc. And among all such positive integers, 7 is the smallest number that has 3 1s in its bit representation.

Input

The input will contain an integer A (0 ≤ A < 1000000).

Output

Print the smallest positive integer that has the same number of 1s in its bit representation as A.

Samples

InputOutput
37
7

Discussion