Binary Function
By Bruno Adami, Universidade de São Paulo - São Carlos 
Brazil
By Bruno Adami, Universidade de São Paulo - São Carlos Brazil
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.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 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 |