你是细菌的爱好者。你想在一个盒子里培养一些细菌。
最初，盒子是空的。每天早上，您可以将任意数量的细菌放入盒子中。而且到第二天早上，盒子里的每个细菌都会分裂成两个细菌。
您希望在某个早上准确地看到盒子中有x个细菌。（当然你也可以在最后的早上，放入一些细菌，使其正好等于x）
请你计算出最少需要放入的细菌数量。
只有一个正整数x（1≤x≤10^9）。
一个正整数表示最少需要放入的细菌数量。
5
2
输入/输出例子2
输入：
8
输出：
1
样例解释
#【样例说明】：
对于第1个样例：可以在第1天早上放入1个细菌，到第3天早上盒子中会有4个细菌，我们可以再添加1个细菌，使其正好为5个细菌。总共放入2个细菌。
对于第2个样例，我们只需在第1天早上放入1个细菌，就会在第4天早上获得8个细菌，所以答案是1。
##【时间限制、数据范围及描述】：
时间：1s 空间：64M
共有10个测试点：
第1个测试点：1≤x≤10；
第2个测试点：1≤x≤10^2；
第3个测试点：1≤x≤10^3；
第4个测试点：1≤x≤10^4；
第5个测试点：1≤x≤10^5；
第6个测试点：1≤x≤10^6；
第7个测试点：1≤x≤10^7；
第8个测试点：1≤x≤10^8；
第9个测试点：1≤x≤10^9；
第10个测试点：1≤x≤10^9；