Степень

Интерпретатор языка программирования Base_ABC умеет выполнять присваивания типа A := B * C (A, B, C - имена некоторых переменных), но не умеет выполнять операцию возведения в натуральную степень. Поэтому вычисления выражения типа A^(N) можно заменить серией команд умножения.

Например, команду X := A^5 можно записать серией из трёх команд

R1 := A * A
R2 := A * R1
X := R1 * R2

За заданным N нужно найти минимальное количество команд присвоения с одним умножением в каждой для вычисления A^N.

Во входном файле число N (2≤N≤2000).

В выходной файл нужно записать одно число - ответ к задаче.

Примеры