Programmers' kids solve this riddle in 5-10 minutes. How fast can you do it?
The input contains a single integer *n* (0 ≤ *n* ≤ 2000000000).
none
11
2
14
0
61441
2
571576
10
2128506
3
0
1
2000000000
4
143165576
14
1741
2
1919020031
3
1795248373
5
1818960378
5
1285316221
3
1309028227
5
1304312649
8
1180540990
5
1204252996
3
1199537418
4
1075765759
2
724264821
5
747976826
4
624205168
4
619489590
4
643201595
5
638486017
6
514714359
3
833393692
3
186925426
4
210637432
4
58438190
4
n = int(input())

r = (
  (1, 0), (2, 0), (3, 0), (4, 1), 
  (5, 0), (6, 1), (7, 0), (8, 2),
  (9, 1), (10, 1), (11, 2), (12, 0),
  (13, 1), (14, 0), (15, 0), (0, 1), )
d = dict(r)

if n == 0 :
  print(1) 
else :
  ans = 0
  while n > 0 :
    p = n -  (n // 16) * 16;
    n //= 16;
    ans += d[p]
  print(ans)
