784_B. Kids' Riddle
Programmers' kids solve this riddle in 5-10 minutes. How fast can you do it?

Input

The input contains a single integer n (0 ≤ n ≤ 2000000000).

Output

Output a single integer.

Examples

Input

11


Output

2


Input

14


Output

0


Input

61441


Output

2


Input

571576


Output

10


Input

2128506


Output

3
```python
a=str(hex(int(input())))
b=0
for i in range(2,len(a)):
    if a[i]=="0" or a[i]=="4" or a[i]=="6" or a[i]=="9" or a[i]=="a" or a[i]=="d":
        b+=1
    elif a[i]=="8" or a[i]=="b":
        b+=2
print(b)

```