Интерпретатор языка программирования Base\_ABC умеет выполнять присваивания типа A := B * C
(A
, B
, C
- имена некоторых переменных), но не умеет выполнять операцию возведения в натуральную степень. Поэтому вычисления выражения типа A^(N)
можно заменить серией команд умножения.
Например, команду X := A^5
можно записать серией из трёх команд
За заданным N
нужно найти минимальное количество команд присвоения с одним умножением в каждой для вычисления A^N
.
Во входном файле число N
(2≤N≤2000
).
В выходной файл нужно записать одно число - ответ к задаче.