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