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