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

Source: codeforces | Difficulty: HARD


Solutions:
val = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'a': 1, 'b': 2, 'c': 0, 'd': 1, 'e': 0, 'f': 0}
ans = 0
for c in hex(int(input()))[2:]:
	ans += val[c]
print(ans)


def count(x):
	if x == '0' or x == '4' or x == '6' or (x == '9') or (x == 'a') or (x == 'd'):
		return 1
	if x == '8' or x == 'b':
		return 2
	return 0
print(sum([count(x) for x in hex(int(input(), 10))[2:]]))


n = int(input())
ans = 1 if n == 0 else 0
while n > 0:
	d = n % 16
	n = n // 16
	if d == 8 or d == 11:
		ans += 2
	elif d == 0 or d == 4 or d == 6 or (d == 9) or (d == 10) or (d == 13):
		ans += 1
print(ans)


p = int(input())
s = hex(p).upper()[2:]
ans = 0
for x in s:
	if x == '0':
		ans += 1
	if x == '8':
		ans += 2
	if x == 'A':
		ans += 1
	if x == 'B':
		ans += 2
	if x == '9':
		ans += 1
	if x == 'D':
		ans += 1
	if x == '4':
		ans += 1
	if x == '6':
		ans += 1
print(ans)


v = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
n = int(input())
a = 1 if n == 0 else 0
while n > 0:
	a += v[n % 16]
	n //= 16
print(a)


print(sum(['046889ABBDabbd'.count(x) for x in hex(int(input()))]) - 1)


a = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
x = int(input())
b = 0
if x == 0:
	b += 1
while x:
	b += a[x % 16]
	x //= 16
print(b)


H = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
n = int(input())
print(sum((H[h] for h in f'{n:X}')))


TASK = 'stars'
a = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
ans = 0
n = int(input())
if n == 0:
	print(1)
	exit()
while n > 0:
	tmp = n % 16
	ans += a[tmp]
	n //= 16
print(ans)


x = [0, 4, 6, 8, 8, 9, 10, 11, 11, 13]
n = int(input())
ret = 1 if n == 0 else 0
while n:
	ret += x.count(n - n // 16 * 16)
	n = n // 16
print(ret)


def to_hex(n):
	return hex(n)[2:].upper()

def closed_loops(x):
	d = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
	total = 0
	a = to_hex(x)
	for c in a:
		total += d[c]
	return total

def main():
	n = int(input())
	print(closed_loops(n))
main()


s = int(input())
a = hex(s)[2:]
print(a.count('0') + a.count('4') + a.count('6') + a.count('8') * 2 + a.count('a') + a.count('9') + a.count('b') * 2 + a.count('d'))


def count(x):
	if x == 0:
		return 1
	ans = 0
	holes = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
	while x:
		ans += holes[x % 16]
		x //= 16
	return ans
print(count(int(input())))


a = int(input())
dirdict = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
kals = str(hex(a)).upper()[2:]
ans = 0
for i in kals:
	ans += dirdict[i]
print(ans)


x = int(input())
t = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
if x == 0:
	print('1')
	exit(0)
y = 0
while x > 0:
	y += t[x % 16]
	x //= 16
print(y)


n = int(input())
a = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']
b = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
s = hex(n)
l = 0
for i in range(2, len(s)):
	l += b[a.index(s[i])]
print(l)


s = hex(int(input()))[2:].upper()
x = 0
x += s.count('0')
x += s.count('4')
x += s.count('6')
x += s.count('8') << 1
x += s.count('9')
x += s.count('A')
x += s.count('B') << 1
x += s.count('D')
print(x)


n = hex(int(input()))[2:].upper()
q = n.count('0') * 1
q += n.count('4') * 1
q += n.count('6') * 1
q += n.count('8') * 2
q += n.count('9') * 1
q += n.count('A') * 1
q += n.count('B') * 2
q += n.count('D') * 1
print(q)


x = int(input())
s = hex(x).split('x')[-1]
ans = 0
for c in s:
	if c in '0469ad':
		ans += 1
	elif c in '8b':
		ans += 2
print(ans)


a = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'a': 1, 'b': 2, 'c': 0, 'd': 1, 'e': 0, 'f': 0}
s = 0
for i in hex(int(input())).replace('0x', ''):
	s += a[i]
print(s)


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)


import sys
mp = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
for line in sys.stdin:
	N = hex(int(line)).upper()
	ans = 0
	for c in N[2:]:
		ans += mp[c]
	print(ans)


D = {0: 1, 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}
n = int(input())
a = 0
if n == 0:
	a = 1
while n > 0:
	a += D[n % 16]
	n //= 16
print(a)


N = int(input())
str = hex(N)[2:]
one = {'0', '4', '6', '9', 'a', 'd'}
two = {'8', 'b'}
ans = 0
for i in range(len(str)):
	if str[i] in one:
		ans += 1
	elif str[i] in two:
		ans += 2
print(ans)


x = int(input(''))
x = hex(x)[2:]
one = ['0', '4', '6', '9', 'a', 'd']
two = ['8', 'b']
count = 0
for i in x:
	if i in one:
		count += 1
	elif i in two:
		count += 2
print(count)


def mp():
	return map(int, input().split())
k = int(input())
if k == 0:
	print(1)
else:
	abc = '0123456789ABCDEF'
	r = 0
	while k > 0:
		d = abc[k % 16]
		if d in '0469AD':
			r += 1
		elif d in '8B':
			r += 2
		k //= 16
	print(r)


import string
n = int(input())
h = str(hex(n))
h = h[2:].upper()
loop = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
s = 0
for i in range(len(h)):
	ch = h[i]
	s += loop[ch]
print(s)


n = int(input())
n = hex(n)[2:]
x = n.count('0') + n.count('4') + n.count('6') + n.count('9')
x += n.count('a') + n.count('d') + n.count('8') * 2 + n.count('b') * 2
print(x)


n = int(input())
summa = 0
first = True
while n > 0 or first:
	first = False
	x = n % 16
	n //= 16
	if x == 4 or x == 0 or x == 6 or (x == 9) or (x == 10) or (x == 13):
		summa += 1
	if x == 8 or x == 11:
		summa += 2
print(summa)


a = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
s = str(hex(int(input())))[2:]
ans = 0
for c in s:
	ans += a[int(c, 16)]
print(ans)


cur = int(input())
hex = ''
shit = ['A', 'B', 'C', 'D', 'E', 'F']
if cur == 0:
	print(1)
	exit(0)
while cur != 0:
	temp = cur % 16
	cur = cur // 16
	if temp >= 10:
		hex += shit[temp - 10]
	else:
		hex += str(temp)
answ = 0
for a in hex:
	if a == 'A' or a == '6' or a == '0' or (a == 'D') or (a == '4') or (a == '9'):
		answ = answ + 1
	elif a == '8' or a == 'B':
		answ += 2
print(answ)


n = hex(int(input()))[2:]
sum = 0
for i in n:
	sum += [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0][int(i, 16)]
print(sum)


import sys
a = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
n = int(input())
if n == 0:
	print(1)
	sys.exit(0)
s = 0
while n:
	s += a[n % 16]
	n //= 16
print(s)


n = int(input())
a = []
if n == 0:
	a.append(0)
while n > 0:
	a.append(n % 16)
	n //= 16
b = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
ans = 0
for x in a:
	ans += b[x]
print(ans)


def f(i):
	if i in '0964ad':
		return 1
	if i in '8b':
		return 2
	return 0
n = sum([f(i) for i in hex(int(input()))[2:]])
print(n)


zc = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
n = int(input())
if n == 0:
	print(1)
else:
	sum = 0
	while n:
		sum += zc[n % 16]
		n //= 16
	print(sum)


a = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
n = int(input())
c = 0
while True:
	k = n % 16
	c += a[int(k)]
	n /= 16
	n = int(n)
	if n == 0:
		break
print(c)


n = int(input())
hex = ''
if n == 0:
	hex = '0'
while n:
	if n % 16 <= 9:
		hex += str(n % 16)
	else:
		hex += chr(n % 16 + 55)
	n //= 16
cnt = 0
for i in hex:
	if i in ['4', '6', '9', '0', 'A', 'D']:
		cnt += 1
	elif i in ['8', 'B']:
		cnt += 2
print(cnt)


a = int(input())
h = hex(a)
s = str(h)[2:]
oneHole = ['0', '4', '6', '9', 'a', 'd']
twoHoles = ['8', 'b']
count = 0
for i in range(len(s)):
	if s[i] in oneHole:
		count += 1
	elif s[i] in twoHoles:
		count += 2
print(count)


n = str(hex(int(input())))[2:]
nums = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1]
ch = [1, 2, 0, 1, 0, 0]
ans = 0
for i in n:
	if i >= '0' and i <= '9':
		ans += nums[ord(i) - ord('0')]
	else:
		ans += ch[ord(i) - ord('a')]
print(ans)


def main():
	n = int(input())
	n = hex(n)[2:]
	ans = 0
	for c in n:
		if c == '0' or c == '6' or c == '9' or (c == 'a') or (c == 'd') or (c == '4'):
			ans += 1
		if c == '8' or c == 'b':
			ans += 2
	print(ans)
main()


def main():
	(n,) = read()
	n = hex(n).upper()[2:]
	dc = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
	sm = 0
	for c in n:
		if ord(c) < 58:
			sm += dc[ord(c) - 48]
		else:
			sm += dc[ord(c) - 65 + 10]
	print(sm)

def read(callback=int):
	return list(map(callback, input().strip().split()))

def write(value, end='\n'):
	if value is None:
		return
	try:
		if not isinstance(value, str):
			value = ' '.join(map(str, value))
	except:
		pass
	print(value, end=end)
write(main())


n = int(input())
hexa = hex(n)
x = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'a': 1, 'b': 2, 'c': 0, 'd': 1, 'e': 0, 'f': 0}

def toInt(c):
	return x[c]
print(sum(map(toInt, hexa[2:])))


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)


a = int(input())
b = str(hex(a)).upper()
l = list(b)
count = -1
for i in l:
	if i == '8' or i == 'B':
		count += 2
		continue
	if i == '0' or i == '4' or i == '6' or (i == '9') or (i == 'A') or (i == 'D'):
		count += 1
		continue
if count < 0:
	count = 0
print(count)


t = (1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0)
print(sum((t[int(i, 16)] for i in '{:X}'.format(int(input())))))


cnt = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
val = int(input())
li = []

def foo(num):
	if num < 16:
		li.append(num)
		return
	foo(num // 16)
	li.append(num % 16)
ans = 0
foo(val)
for d in li:
	ans += cnt[d]
print(ans)


cnt = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
a = int(input())
hexStr = hex(a).replace('0x', '').upper()
ans = sum([cnt[x] for x in hexStr])
print(ans)


f = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
n = '%X' % int(input())
s = 0
for i in n:
	s += f[i]
print(s)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	n = I()
	s = hex(n).upper()[2:]
	r = 0
	for c in s:
		if c in '8B':
			r += 2
		elif c in '0469AD':
			r += 1
	return r
print(main())


d = {'0': 1, '4': 1, '6': 1, '8': 2, '9': 1, 'A': 1, 'B': 2, 'D': 1}
n = int(input())
print(sum((d[c] for c in '{:X}'.format(n) if c in d)))


holes = {'0': 1, '1': 0, '2': 0, '3': 0, '4': 1, '5': 0, '6': 1, '7': 0, '8': 2, '9': 1, 'A': 1, 'B': 2, 'C': 0, 'D': 1, 'E': 0, 'F': 0}
n = int(input())
print(sum((holes[x] for x in '{:X}'.format(n))))


n = int(input())
s = hex(n)
x = 0
for c in s[2:]:
	if c == '0':
		x += 1
	if c == '4':
		x += 1
	if c == '6':
		x += 1
	if c == '8':
		x += 2
	if c == '9':
		x += 1
	if c == 'a':
		x += 1
	if c == 'b':
		x += 2
	if c == 'd':
		x += 1
print(x)


n = int(input())
sumx = 0
if n == 0:
	print(1)
else:
	while n > 0:
		a = n % 16
		if a < 10:
			if a == 0 or a == 4 or a == 6 or (a == 9):
				sumx += 1
			elif a == 8:
				sumx += 2
		elif a == 10 or a == 13:
			sumx += 1
		elif a == 11:
			sumx += 2
		n = n // 16
	print(sumx)


rings = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]

def cnt(n):
	if n:
		res = 0
		while n:
			res += rings[n % 16]
			n //= 16
	else:
		res = 1
	return res
n = int(input())
print(cnt(n))


n = hex(int(input()))
n = n[2:]
t = 0
for i in range(0, len(n)):
	if n[i] == 'a':
		t += 1
	if n[i] == 'b':
		t += 2
	if n[i] == 'd':
		t += 1
	if n[i] == '0':
		t += 1
	if n[i] == '4':
		t += 1
	if n[i] == '6':
		t += 1
	if n[i] == '8':
		t += 2
	if n[i] == '9':
		t += 1
print(t)


val = [1, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 0, 1, 0, 0]
n = int(input())
x = hex(n)
x = x[2:]
ans = 0
for i in x:
	i = int(i, 16)
	ans = ans + val[i]
print(ans)


def count(s):
	res = 0
	for i in s:
		if i in ['0', '4', '6', '9', 'A', 'D']:
			res += 1
		elif i in ['8', 'B']:
			res += 2
	return res

def main():
	s = hex(int(input())).replace('0x', '').upper()
	print(count(s))
main()


x = hex(int(input()))[2:].upper()
one = set(['A', 'D', '0', '4', '6', '9'])
two = set(['B', '8'])
count = 0
for i in x:
	if i in one:
		count += 1
	elif i in two:
		count += 2
print(count)


o = ['0', '4', '6', '9', 'a', 'd']
oo = ['8', 'b']
cnt = 0
n = list(hex(int(input())))
x = ''
for i in range(2, len(n)):
	x += n[i]
x = str(x)
for j in x:
	if j in o:
		cnt += 1
	elif j in oo:
		cnt += 2
print(cnt)