Ханойские башни - перезагрузка
В одном из храмов индийского города Бенареса установлена бронзовая плита с тремя алмазными стержнями. При сотворении мира верховный индуистский бог Брахма поместил на первый стержень 64 диска из чистого золота, в порядке уменьшения их размеров, и велел монахам переместить их на третий стержень, запретив при этом за один раз переносить более одного диска и помещать больший диск на меньший. С тех пор монахи день и ночь, сменяя друг друга, трудятся над этой задачей. Как только задача будет решена, храм рассыплется в прах и завершится жизнь Брахмы. Затем родится новый Брахма, и всё повторится...
Да, пока вы не успели поверить в то, что монахи индуистского монастыря действительно занимаются решением этой головоломки, спешу сообщить, что это всего лишь легенда. Причем вовсе не древняя, как большинство известных легенд. Придумал ее в конце XIX века французский математик Эдуард Люка. Красивая история оказалась очень удачным рекламным трюком для "раскрутки" (как сказали бы современные PR-менеджеры) придуманной Люка изящной головоломки, выполненной из дерева и состоящей из восьми дисков. Начиная с 1883 года она продавалась под разными названиями — "Башни Брахмы", "Головоломка о конце света", "Пагода-головоломка", да и место действия легенды неоднократно переносилось то в Китай, то в Тибет, но в итоге "прижилось" во Вьетнаме — вместе с названием "Ханойские башни".
Когда же завершится жизнь очередного нового Брахмы, с учётом того, что он обязательно учтёт опыт своего предшественника и дисков у монахов однозначно будет больше?
Входные данные
Единственное число - количество дисков n (64 ≤ n ≤ 10000), выданное монахам очередным Брахмой.
Выходные данные
Единственное число - минимальное количество перекладываний, необходимое монахам для переноса башни с 1-го стрежня на 3-й в оптимальном режиме.