Zirək və bacarıqlı tikməçi muncuq dənələrindən simurq (əfsanəvi quş) hazırlamaqla əlavə qazanc əldə etməyi qərara aldı. İncəsənətdə simmetriyanı sevdiyindən o, öz ornamentində müxtəlif rəngli muncuqlardan aşağıdakı qaydada istifadə edirdi(rəngləri tam müsbət ədədlə işarə edəcəyik): 1) naxışın uzunluğu 1-ə bərabər olan sırasında birinci rəngdə olan muncuqlardan istifadə etmək; 2) naxışın uzunluğu 3-ə bərabər olan sırasında iki rəngli: \textbf{1 2 1} muncuqlardan istifadə etmək; 3) naxışlara daha bir rəngli əlavə naxış vurmaq zəruridirsə, belə sıra düzülür: \textbf{1 2 1 3 1 2 1} və hər dəfə istifadə olunan rənglərin sayından asılı olaraq, məsələn 4 rəngdən istifadə edilirsə, belə olar:\textbf{ 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1}. Sıra nömrəsinə görə sıralarda muncuqların rənginin seçilməsini avtomatlaşdırmağa kömək edən proqramı tərtib edin. \InputFile Birinci sətirdə naxışların sırasındakı rəngini müəyyənləşdirmək lazım olan muncuğun nömrəsi olan bir tam \textbf{k} (\textbf{1} ≤ \textbf{k} ≤ \textbf{10^9}) ədədi verilir. Sırada muncuqların nömrəsi birdən başlayır. \OutputFile Birinci sətirdə verilmiş muncuğun rənginin nömrəsi olan bir tam ədəd verilir.