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