A rotary encoder emits positions using the standard reflected binary Gray code (consecutive positions differ in exactly one bit). Each physical position k (starting from 0) produces the code g = k XOR (k >> 1).
Given a code value g that the encoder produced, recover the position index k, i.e. the unique non-negative integer such that k XOR (k >> 1) = g.
Input format
Line 1: an integer g.
Output format
A single integer: the position index k that maps to the Gray code g.
Constraints
- 0 <= g <= 100000