f = lambda n:bin(n^n/2).count('1')

for n in (0, 1, 42, 97, 170, 255, 682, 8675309, 4812390, 178956970, 2863311530):
	print '%10d -> %2d' % (n, f(n))