Description

你有一个数字 $1$，你可以对它进行若干次操作。每次操作要么把它乘以 $2$，要么把它加上 $1$，请问至少几次操作可以让它恰好等于 $n$

Format

Input

输入一行一个正整数。

Output

输出一行一个正整数表示答案。

Samples

3

2

15

6

Sample 2 explain

先做两次加一运算得到 $3$，然后做一次乘二运算得到 $6$，然后做一次加一运算得到 $7$，做一次乘二运算得到 $14$，再加一得到 $15$，共 $6$ 次运算

Limitation