Заповзята та вміла рукодільниця вирішила підзаробити виготовленням <<фенечок>> з бісеру. Як любитель симетрії в мистецтві, вона використовувала у своїх орнаментах бусинки різних кольорів (будемо позначати колір цілим додатним числом) за наступними правилами: 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 У єдиному рядку вивести одне ціле число -- номер кольору заданної бусинки.