题目描述
你是细菌的爱好者。你想在一个盒子里培养一些细菌。

最初，盒子是空的。每天早上，您可以将任意数量的细菌放入盒子中。而且到第二天早上，盒子里的每个细菌都会分裂成两个细菌。

您希望在某个早上准确地看到盒子中有 x 个细菌。（当然你也可以在最后的早上，放入一些细菌，使其正好等于 x ）

请你计算出最少需要放入的细菌数量。

输入格式
一个正整数 x 。

数据范围
1 ≤ x ≤ 10^9

输出格式
一个正整数表示最少需要放入的细菌数量。

样例

5

2

8

1

样例解释
样例1：可以在第1天早上放入1个细菌，到第3天早上盒子中会有4个细菌，我们可以再添加1个细菌，使其正好为5个细菌。总共放入2个细菌。
样例2：我们只需在第1天早上放入1个细菌，就会在第4天早上获得8个细菌，所以答案是1。