Задачі
Симетрія
Симетрія
Заповзята та вміла рукодільниця вирішила підзаробити виготовленням <<фенечок>> з бісеру. Як любитель симетрії в мистецтві, вона використовувала у своїх орнаментах бусинки різних кольорів (будемо позначати колір цілим додатним числом) за наступними правилами:
1) при довжині ряду візерунку рівній \textbf{1} використовувала бусинку першого кольору;
2) при довжині ряду візерунку рівній \textbf{3} використовувала бусинки двох кольорів: \textbf{1 2 1};
3) при необхідності додавання у візерунок ще одного кольору будувався ряд: \textbf{1 2 1 3 1 2 1} і так щоразу в залежності від числа використовуваних кольорів, наприклад, при використанні чотирьох кольорів: \textbf{1 2 1 3 1 2 1 4 1 2 1 3 1 2 1}.
Напишіть програму, яка допомогла б автоматизувати підбір кольору бусинки в ряду за її порядковим номером.
\InputFile
У першому рядку задано ціле число \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^9}) -- номер бусинки, колір якої потрібно визначити, в рядку візурунку. Нумерація бусинок в рядку починається з одиниці.
\OutputFile
У єдиному рядку вивести одне ціле число -- номер кольору заданної бусинки.
Вхідні дані #1
10
Вихідні дані #1
2