Предприимчивая и умелая рукодельница решила подзаработать изготовлением <<фенечек>> из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам: 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 В первой строке одно целое число -- номер цвета заданной бусинки.