Damon was captured by almighty Ni’klaus.
Ni’klaus was 1000 years old and have spent his life hunting innocents, so he didn’t had time to study math.
Damon, a sharp minded vampire, came across a very interesting idea. He wanted to tell his friends the address of the house he is being held captive in, so he called one of them and told him a number. Ni’klaus being an original vampire have splendid capability of hearing, heard the number but was carefree as he knew it was not the number of the house they were in.
But as already mentioned Damon was smart and his friends too. Damon gave his friend the number in a special encrypted format. He expected his friend to convert the number into binary and add the number of 1’s.
The number of 1’s in the number will be the house number he is trapped in.

Input
First line contains T number of test cases. T test cases the follows
Each test contains a number N

Output
Print in new line the house number.

Constraints

1 ≤ T ≤ 100
2 ≤ number given by Damon ≤ 10^9

Example
Input:
2
2
15
Output:
1
4

见题面

见题面