the-magic

Navi got a  task at school to collect N stones. Each day he can collect only one stone. As N can be a very large number so  it could take many days to complete the task, but then he remembers that his mother gave him a magic that can double anything (i.e if he has 2 stones, the  magic will make them to 4 stones). Navi can use this magic any number of time on the collected stone on a particular day and add this to the previously collected stones. Remember that he wants exactly N stones and he can't throw any stone.  If he gets more than N stones then he gets 0 marks, of course he doesn't want 0 marks. Help him to collect exactly N stones in minimum number of days. 

Input
 First line of input will contain number of test cases (T). Then next T lines contains a single number N, which is number of stones Navi has to collect. 

Output

For each test case, Print a single number which is the minimum number of days taken by Navi to complete the task.  
Constraints
1 ≤ T ≤ 10^5 

0 ≤ N ≤ 10^9 

SAMPLE INPUT
2
1
3

SAMPLE OUTPUT
1
2

Explanation

In the second case when n = 3, he will collect 1 stone on the first day and double it and collect the remaining one on the next day.

Source: hackerearth | Difficulty: EASY
Tags: Ad-hoc


Solutions:
T = int(input())

i = 1

while T >= i:

	N = int(input())

	N = bin(N).count('1')
	
	print(N)
	
	i += 1


from math import log
T=int(input())
for i in range(0,T):
	N=int(input())
	count=0
	while(N!=0):
		temp=int(log(N,2))
		if(temp>0):
			N=N-(2**temp)
		else:
			N=N-1
		count=count+1
	print (count)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def compDays(n):
	c = 0
	while n > 0:
		while n%2 == 0:
			n = n//2
		n = n-1
		c+=1
	return c

T = int(input())
for i in range(T):
	n = int(input())
	a = compDays(n)
	print(a)


t=int(input())
while t:
	t=t-1
	n=int(input())
	no_b=0
	while n:
		if n%2==1:
			no_b+=1
		n=n/2
		
	print(no_b)
	


def days(n):
	if( not(n-(-n&n)) ):
		return 1;
	power=0
	check=False
	i=0
	while(check is False):
		if(2**i > n):
			power=i-1
			check=True
		i+=1

	return 1+days(n-2**power)
t=int(input())
while t:
	t-=1
	n=int(input())
	if(n==0):
		print((0))
	else:
		print((days(n)))
		


T=int(input())
for i in range(0,T):
	N=int(input())
	print((bin(N).count("1")))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name

print 'Hello World!'
'''


def countsetbits(n):
	count = 0
	while (n):
		if (n&1):
			count = count + 1
		n = n >> 1
	return count

t = int(input())

while (t):
	n = int(input())
	count = countsetbits(n)
	t = t -1
	print(count)




for _ in range(eval(input())):
	n = eval(input())
	print(bin(n).count("1"))


#!/usr/local/bin/python

import sys

total_test_cases= int(sys.stdin.readline())
for _ in range(total_test_cases):
	stones_needed = int(eval(input()))
	days_needed = 1
	current_no_of_stones = 0
	while True:
		if stones_needed <=0 :
			break
		if stones_needed % 2 == 0:
			stones_needed = stones_needed / 2
		else:
			days_needed = days_needed + 1
			stones_needed = stones_needed - 1
	print((days_needed-1))


test_c = eval(input())
for i in range(test_c):
	print("{0:b}".format(eval(input())).count('1'))


T = int(input())

for i in range(T):
	N = int(input())
	x = 0
	while N>0:
		x+=1
		N=N&(N-1)
	
	print(x)


def mult(b):
	sum=1
	while 1:
		if sum==b:
			return 1
		sum*=2
		if sum>b:
			return sum/2
		elif sum==b:
			return sum

t=eval(input(""))
while t:
    a=eval(input(""))
    b=a
    count=0
    sum=0
    c=0
    while 1:
    	if sum==a:
    		break
    	b-=c
    	c=mult(b)
    	sum+=c
    	count+=1
    print(count)
    t-=1


t=eval(input(''))
cnt=0
def no_of_one(n):
	cnte=0
	while n:
		n= n &n-1
		cnte+=1
	return cnte

while t>cnt:
	s=eval(input(''))
	print(no_of_one(s))
	t-=1


def TheMagic():
	T = int(input())
	for cas in range(T):
		N = int(input())
		days = 0
		power,rem = 1,N
		while rem:
			while power <= rem:
				power *= 2
			rem -= power/2
			power = 1
			days += 1
		print(days)
		
if __name__ == "__main__":
	TheMagic()


def TheMagic():
	T = int(input())
	for case in range(T):
		N = int(input())
		days = 0
		power,rem = 1,N
		while rem:
			while power <= rem:
				power *= 2
			rem -= power/2
			power = 1
			days += 1
		print(days)
		
if __name__ == "__main__":
	TheMagic()


T=int(input())
for i in range(0,T):
	n=int(input())
	print(bin(n).count('1'))



def decimal_to_binary(a):
	binary = ''
	while(a!=0):
		binary += str(a%2)
		a = a/2
	binary = binary[::-1]
	return binary
T = eval(input())
while T:
	N = eval(input())
	count = 0
	binary = decimal_to_binary(N)
	for i in binary:
		if i == '1':
			count += 1
	print(count)
	T-=1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def set_bits(n):
	ctr = 0
	while n > 0:
		n = n&(n-1)
		ctr += 1
	return ctr

for i in range(eval(input())):
	print(set_bits(eval(input())))


T = int(input())
for t in range(T):
	N = int(input())
	collect =0
	sumi=1
	count= 0
	num  = N
	
	while (collect<N):
	  

		target = (num//2)*2
		if (target==0):
			count+=1
			break

		while sumi<=target:
		 
			sumi=sumi << 1
		sumi = sumi >> 1


		if (collect<N):
			collect+=sumi
			num = N-collect
			sumi= 1
			count+=1
	print(count)

		
		

		


test = eval(input())
while test>0:
	num = eval(input())
	if num==0:
		print(0)
	else:
		day = 0
		total = 0
		while num>total:
			present = 1
			day += 1
			while present <=(num-total):
				present *= 2
			present /= 2
			total += present
		print(day)
	test -= 1


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input())
for _ in range(t):
	n = int(input())
	d = 0
	while(n):
		n = n & (n-1)
		d += 1
	print(d)


test_c = eval(input())
for i in range(test_c):
	print("{0:b}".format(eval(input())).count('1'))


__author__ = 'legion'

iteration = int(input())

for num in range(iteration):
	count = 0
	input_no = int(input())
	while input_no:
		input_no &= input_no - 1
		count += 1
	print(count)




def ConvertToBinary(decimal):
	mylist=list();
	while decimal>1:
		rem=decimal%2
		decimal=decimal/2
		mylist.append(rem)
	mylist.append(decimal)
	return sum(mylist)
T=int(eval(input()))
dayslist=list()
for i in range(0,T):
	N=int(eval(input()))
	days=ConvertToBinary(N)
	dayslist.append(days)
for i in dayslist:
	print(i)


from math import log

for case in range(eval(input())):
	n = eval(input())
	if n == 0:
		print('0')
	elif n == 1:
		print('1')
	else:
		s, i = n, 0
		while s > 0:
			s -= 2**(int(log(s, 2)))
			i += 1
		print(i)