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

输入格式

输入一行一个正整数。

输出格式

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

3

2

15

6

说明

样例 2 说明：先做两次加一运算得到 3，然后做一次乘二运算得到 6，然后做一次加一运算得到 7，做一次乘二运算得到 14，再加一得到 15，共 6 次运算

测试点说明