Given a positive integer n, count the number of set bits in the binary representation of n.

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input has one line containing a positive integer ‘n’.

Output Format

For each test case, the output has one line containing the number of set bits in the binary representation of n.

Sample Input

3
1
5
8

Expected Output

1
2
1

Constraints

1 <= T <= 105
1 <= n <= 109