eolymp
bolt
Try our new interface for solving problems
Problems

Головоломка Мажордома

Головоломка Мажордома

Time limit 0.1 seconds
Memory limit 16 MiB

Мажордом был хитрым и достаточно образованным человеком. По словам Чосера, "так овцам счет умел вести он, акрам и так подчистить свой амбар иль закром, что сборщики все оставались с носом. Он мог решать сложнейшие вопросы..."

Поэт отмечает также, что "он никогда не попадал впросак". Всякого рода забавные задачи и причудливые идеи без труда возникали в его остром уме. В одной придорожной таверне, где остановились паломники, его бдительный взор обнаружил несколько кругов сыра разной величины. И вот, попросив четыре табурета, он предложил показать одну из своих головоломок, которая могла бы позабавить путников во время отдыха. Затем Мажордом положил на крайний табурет восемь кругов сыра так, как это показано на рисунке.

- Вот загадка, - воскликнул он, - которую я задал однажды своим приятелям из Болдсуэлла, что находится в Норфолке, и, клянусь святым Иосифом, среди них не нашлось ни одного, кто осилил бы ее! Однако она очень проста, ибо все, что я хочу, так это чтобы, перекладывая сыры с одного табурета на другой, вы перенесли все их на табурет, стоящий на другом конце, ни разу не переложив какой-нибудь круг сыра на круг меньшего размера. Того, кто сумеет это сделать с наименьшим числом перекладываний, угощу я глотком самого лучшего вина, какое только найдется у нашего доброго хозяина.

А за какое минимальное количество перекладываний сможете Вы решить задачку Мажордома? И как быстро?

Input data

В каждой строке входного файла задано единственное число n (1n255) - количество сыров на первом табурете. Входные данные считывать до конца файла.

Для каждого числа из входных данных в отдельной строке выведите единственное число - ответ на задачку Мажордома.

Examples

Input example #1
8
10
21
3
Output example #1
33
49
321
5
Author Анатолий Присяжнюк