Задачи
Ханойские башни с четырьмя стержнями
Ханойские башни с четырьмя стержнями
Обратитесь к описанию классической задачи о Ханойских башнях с тремя стержнями.
Сейчас мы расширим задачу о Ханойских башнях, в которой будет четыре стержня и запрос вида "\textit{Какое наименьшее количество перекладываний дисков следует совершить для решения задачи о Хайнойских башнях для заданного }\textit{\textbf{n}}\textit{, если у нас имеется четыре стержня вместо трех?}" Сохраним правила перемещения \textbf{n }дисков с одного стержня на другой, в которых не разрешается больший диск класть на меньший. Новым является то, что в наличии имеется два вспомогательных стержня, а не один.
Например, для перекладывания трех\textbf{ }дисков со стержня \textbf{A} на \textbf{D} можно поступить так: диск \textbf{1} с \textbf{А} на \textbf{В}, диск \textbf{2} с \textbf{А }на \textbf{С}, диск \textbf{3} с \textbf{А} на \textbf{D}, диск \textbf{2} с \textbf{С} на \textbf{D}, и диск \textbf{1} с \textbf{B} на \textbf{D}, совершив таким образом \textbf{5} перекладываний.
\InputFile
Каждая строка содержит одно целое число \textbf{n}, не большее \textbf{1000}. Для каждого значения \textbf{n} следует найти наименьшее количество перекладываний дисков для решения задачи о Ханойских башнях с четырьмя стержнями. Обработка данных завершается концом файла.
\OutputFile
Вывести наименьшее количество перемещений дисков для решения задачи. Формат вывода: "\textbf{Case}", один пробел, номер теста, двоеточие, один пробел и ответ для этого теста. Известно, что ответ помещается в \textbf{64}-битовый целочисленный тип. Не следует выводить конечных пробелов.
Входные данные #1
1 3 5
Выходные данные #1
Case 1: 1 Case 2: 5 Case 3: 13