Description

一个整数A可以写成2的幂次方多项式： A = A02^0 + A12^1 + A22^2 + … + An2^n Ai=0或1 给定一个整数，确定有几个Ai为非0值。

Input

输入有一些整数A（0<=A<2^32）。

Output

对每个整数给出其非0的Ai个数。

Sample

Input

2 3 9

Output

1
2
2