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.

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.

For each test case, Print a single number which is the minimum number of days taken by Navi to complete the task.

1 <= T <= 10^5

0 <= N <= 10^9

2

1

3

2

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.

**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.

**C Implementation:**/* logic is counting the number of ones*/ #include <stdio.h> int ones(int n) { int count = 0; while(n) { if(n&1) count++; n>>=1; } return count; } int main() { int t; int n; scanf("%d",&t); while(t--) { scanf("%d",&n); printf("%d\n",ones(n)); } return 0; }