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