说明

给定一个数n，你可以进行若干次操作，每次操作可以翻转n的二进制表示下的某一位，即将0变成1，1变成0。 请问：至少需要多少次操作，才能将n变成n−1。

输入格式

一个正整数n。(1<n≤10⁹)

输出格式

输出最少的操作次数。

样例

10

2

提示

样例说明：

10 的二进制是 1010

9 的二进制是  1001

因此最少需要两步：

    1010 -> 1000 -> 1001