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.
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(raw_input())
while t:
    t-=1
    n=int(raw_input())
    if(n==0):
    	print(0)
    else:
    	print(days(n))