Symmetry
An enterprising and skilled craftswoman decided to earn some extra money by making bead "bracelets." As a lover of symmetry in art, she used beads of different colors in her patterns (we will denote the color by a positive integer) according to the following rules:
1) For a pattern row length of **1**, she used a bead of the first color;
2) For a pattern row length of **3**, she used beads of two colors: **1 2 1**;
3) When adding another color to the pattern, the row was constructed as: **1 2 1 3 1 2 1**, and so on depending on the number of colors used. For example, when using four colors: **1 2 1 3 1 2 1 4 1 2 1 3 1 2 1**.
Write a program that helps automate the selection of the bead color in the row by its ordinal number.
Input
The first line contains an integer **k** (**1** ≤ **k** ≤ **10^9**) – the number of the bead whose color needs to be determined in the pattern row. The numbering of beads in the row starts from one.
Output
Output a single integer on one line – the color number of the specified bead.