Зустрів якось Іван чорта. Чорт запропонував Івану перейти через міст, і тоді сума грошей у нього подвоїться. Але після кожного переходу Іван  повинен заплатити чорту N золотих.

Після четвертого переходу виявилось, що грошей у Івана рівно стільки, щоб заплатити чорту. Скільки грошей було у Івана спочатку? Відомо, що всі грошові суми були цілими.

Технічні умови

Програма Bridge вводить з клавіатури натуральне число N (N<=1000000). Програма виводить на екран початкову кількість золотих.

Приклад

Введення    Виведення

48                   45