Description

一个十进制数，总是可以表示成不同的2的幂次方的和。例如：13=2^3+2^2+2^0。现在关心的是其项数，13是由3个不同的2幂次方累加而得，同样，14是由另一组3个不同的2幂次方累加而得。那么，给出任意一个整数，你能告诉我有多少个不同的2幂次方累加而得吗？

Input

一些整数n（1≤n≤2^31），若遇到0，则结束。

Output

对应每个整数，以一行一个的格式，输出其不同的2幂次方个数。

Sample

Input

13 14 6 0

Output

3
3
2

Source: qn