A rotating beacon steps through the standard reflected binary Gray code: an ordering of the non-negative integers in which consecutive entries differ in exactly one bit. The sequence begins 0, 1, 3, 2, 6, 7, 5, 4, ... and is defined recursively by reflection (list the first block, then the same block reversed with the next-higher bit prepended).

Given a 0-indexed position k, output the value that sits at position k of this sequence.

Input format

Line 1: an integer k.

Output format

A single integer: the k-th value of the reflected Gray code sequence.

Constraints

• 0 <= k <= 100000

5

7

0

0