Интерпретатор языка программирования 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).

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