В одному з буддійських монастирів монахи вже тисячу років займаються перекладуванням дисків. У своєму розпорядженні вони мають три стержні, на які надіто диски різних розмірів. У початковому стані якась кількість дисків було надіта на лівий стержень і впорядковані за розміром - від менших до більших зверху донизу. Монахи повинні перекласти усі диски з першого стержня на третій, дотримуючись єдиної умови – довільний диск не можна покласти на диск меншого розміру. При перекладуванні можна використовувати усі три стержні. Монахи перекладують один диск за одну секунду. Як тільки вони завершать свою роботу, настане кінець світу.

Ну хіба ж це по-монашому, наближати кінець світу? Неправильні якісь монахи... :)

Тому нас не буде цікавити відповідь на питання, якимось чином пов'язане з апокаліпсисом, а буде цікавити відповідь на більш звичне у буденному нашому житті питання: А за яку найменшу кількість перекладувань монахи зможуть завершити свою работу, при умові, що перекладають вони диски оптимальним чином?

Вхідні дані

Кількість дисків n (0 ≤ n ≤ 64), які є у розпорядженні монахів. За дивним збігом обставин число дисків у цій задачі не перевищує кількості клітинок на звичній шаховій дошці.

Вихідні дані

Найменша кількість перекладань, за яку монахи зможуть завершити свою роботу.