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