Новогодняя елка украшена гирляндой бесконечной длины, которая состоит из последовательно соединенных лампочек. Когда гирлянду включают, загорается только первая лампочка, считая от выключателя, которая горит одну секунду. Далее гирлянда начинает мигать по следующему правилу. Каждую секунду для каждой лампочки проверяется условие: если ровно одна из ее соседних лампочек горит, то эта лампочка будет гореть на следующей секунде; иначе – не будет гореть. У первой лампочки только одна соседняя.

Напишите программу, которая по номеру секунды находит количество лампочек гирлянды, которые будут гореть на протяжении этой секунды.

Входные данные

Одно целое число n (1 ≤ n ≤ 109) - номер секунды.

Выходные данные

Вывести одно целое число - количество лампочек, которые будут гореть на секунде n.