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.

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 (Plaintext Link)

2 1 3

Sample Output (Plaintext Link)

`1`

`2`

`Explanation : `

`When N = 1, in 1 day he can collect stone.`

```
When N = 3, on 1st day he collect 1 stone, make it double. so now he has 2.
On day 2, he can collect one , so total now he has collected 3 stones in 2 days.
```

` `

`Code Solution : `

` `

**#include <stdio.h>
int main(){
int T,N,stone,remaining,day;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
day=1;
remaining=N;
while(1)
{
if(remaining==1)
break;
if(remaining==0)
{day--; break;}
stone=1;
while( (stone*2) <= remaining){
stone = 2*stone;
}
remaining = remaining - stone;
day++;
}
printf("%dn",day);
}
return 0;
}**