URI Online Judge | 1593

Binary Function

By Bruno Adami, Universidade de São Paulo - São Carlos BR Brazil

Timelimit: 1

We define the parity of an integer as the sum of its bits in the binary form modulo two. Take this example, the number 2110 = 101012 has three 1's in its binary representation and thus it has an odd parity.

In this problem, you need to calculate the number of bits 1 in an integer I given in the input, it is, calculate the number of 1's in the binary representation.

Input

The first line contains an integer T (T <= 100) indicating the number of test cases.

For each case, there will be a single line with the number I (1 ≤ I < 1018* or 1 ≤ I < 101000**).The input number won't have leading zeroes.

*for around 90% of the cases;
**for the other test cases.

Output

Output the number of 1's in the binary representation for each case in a single line.

Sample Input Sample Output

3

21

3

123456789123456789123456789

3

2

50