Yeni il yolkası sonsuz uzunluqlu ardıcıl birləşdirilmiş lampalardan ibarət hörükşəkilli bəzəklə bəzədilmişdir. Bəzək işə salındıqda elektrik açarının yanından başlayaraq yalnız birinci lampa bir saniyə yanır. Sonra bəzəyin işıqları aşağıdakı qayda ilə sayrışır.

Hər saniyədə hər lampa üçün aşağıdakı şərt yoxlanılır: əgər lampanın qonşularından yalnız biri yanırsa, onda bu lampa növbəti saniyədə yanacaq, əks halda isə yanmayacaq. Birinci lampanın yalnız bir qonşusu var.

Saniyənin nömrəsinə görə həmin saniyə ərzində yanacaq bəzək lampalarının sayını tapan GARLAND proqramını yazın.

Giriş verilənləri

Yeganə sətirdə saniyənin nömrəsi olan bir n (1 ≤ n ≤ 109) tam ədədi verilir.

Çıxış verilənləri

Yeganə sətirdə n-ci saniyədə yanan bütün lampaların sayını göstərən tam ədədi çap edin.