Интерпретатор языка программирования 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). В выходной файл нужно записать одно число – ответ к задаче.