In all known classical problem of the Tower of Hanoi assume discs numbered consecutive numbers starting from zero so that the disk with a larger diameter corresponded to a greater number.

Our task - for a given serial number (numbered from 1) the correct solution to determine the serial number of the disk, which made this move.

We believe that the original number of drives is enough for the demanded number of moves.

Input

The only line of input contains the number n (1 ≤ n ≤ 263) we are interested in running.

Output

Print the serial number of the disk, which made n-th move.