Інтерпретатор мови програмування Base_ABC вміє виконувати присвоювання типу A := B × C (A, B, C — імена деяких змінних), але не вміє виконувати операцію піднесення до натурального степеня. Тому обчислення виразу типу AN можна замінити серією команд множення. Наприклад, команду X := A5 можна записати серією з трьох команд:

R1 := A × A

R2 := A × R1

X := R1 × R2

По заданому N потрібно знайти мінімальну кількість команд присвоювання з одним множенням у кожній для обчислення AN.

У вхідному файлі число N (2 ≤ N ≤ 2000). До вихідного файлу потрібно записати одне число — відповідь до задачі.