权势二进制

一个十进制整数被叫做权势二进制，当他的十进制表示的时候只由0或1组成。例如0,1,101,110011都是权势二进制，而2,12,900不是。当给定一个n的时候，计算一下最少要多少个权势二进制相加才能得到n。

输入

第一行一个整数n（1<=n<=1000000）

输出

一行，表示个数

样例

6237

7