你是一个细菌爱好者，你想在盒子里养一些细菌。

首先，盒子是空的。每一个早晨，你可以把任何数量的细菌放进盒子里。每一天晚上盆子里的每一个细菌都会分裂成两个细菌，你希望看到盒子里有X个细菌。

在这些日子里，你需要放入盒子里的细菌的最小数量是多少?

一个整数x(1<=x<=10^9)

一个整数

样例2输入

8

样例2输出

1

提示：

对于第一个样例，我们可以在第一天早上在盒子里加一个细菌 第三天早上盒子里会有4个细菌。现在我们在盒子里再放一个结果5。我们在这个过程中加入了2个细菌，所以答案是2.

对于第二个样例，我们可以在第一个早晨放一个，在第四个早晨盒子里将有8个，所以答案是1.

吕扬涛2021