Symmetry#165
An enterprising and skilled craftswoman decided to earn some money by making bead bracelets. Being a fan of symmetry in art, she arranged beads of different colors (color is denoted by a positive integer) according to the following rules:
1) For a pattern row of length , she used a bead of the first color;
2) For a pattern row of length , she used beads of two colors: ;
3) If it was necessary to add one more color to the pattern, the row was constructed as: 1\ 2\ 1\ 3\ 1\ 2\ 1; each time, depending on the number of used colors, for example, with four colors: 1\ 2\ 1\ 3\ 1\ 2\ 1\ 4\ 1\ 2\ 1\ 3\ 1\ 2\ 1.
Write a program that determines the color of the bead at a given position in the row.
The first line contains an integer (1 \leq k \leq 10^9) — the position of the bead whose color must be determined. Bead positions are numbered starting from one.
Output a single integer — the color number of the specified bead.
Example 1