你是细菌爱好者。你想在盒子里培养一些细菌。
最初,盒子是空的。每天早上,您可以将任意数量的细菌放入盒子中。每天晚上,盒子里的每个细菌都会分裂成两个细菌。你希望在某个时刻能在盒子里看到 x 个细菌。
这些天您需要在盒子中放入的最少细菌数量是多少?
输入
唯一包含一个整数 x (1 ≤ x ≤ 109) 的行。
输出
唯一包含一个整数的行:答案。
示例
输入 #1
5
输出 #1
2
输入 #2
8
输出 #2
1
注意
对于第一个样品,我们可以在第一天早上在盒子里添加一个细菌,到第三天早上盒子里就会有 4 个细菌。现在我们在框中再放入一个结果 5。我们在这个过程中添加了 2 个细菌,所以答案是 2。
对于第二个样品,我们可以在第一个早上放一个,第四天早上盒子里会有 8 个。所以答案是1。